문제
2ドル$차원 평면 위에 $N$개의 점이 주어진다. 선분 $N - 1$개를 그어 트리를 만드시오. 단, 그은 선분 중 어떠한 두 선분도 서로 교차하면 안 된다.
어떤 선분의 끝점이 다른 선분 위에 있는 것은 교차하는 경우이다. 두 선분이 끝점에서 만나는 것은 교차하는 경우가 아니다.
출력
$N - 1$개의 줄에 걸쳐 트리를 구성하는 선분을 출력한다. 각 줄에는 선분을 이루는 두 점의 번호를 공백으로 구분하여 출력한다.
트리를 긋는 방법이 여럿인 경우는 그중 아무거나 하나를 출력한다.
예제 출력 2
1 4
2 4
4 3
3 5
5 6
5 7
W3sicHJvYmxlbV9pZCI6IjI5NzU3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkMmI4XHViOWFjIFx1YWUwYlx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+JDIkXHVjYzI4XHVjNmQwIFx1ZDNjOVx1YmE3NCBcdWM3MDRcdWM1ZDAgJE4kXHVhYzFjXHVjNzU4IFx1YzgxMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzEyMFx1YmQ4NCAkTiAtIDEkXHVhYzFjXHViOTdjIFx1YWRmOFx1YzViNCBcdWQyYjhcdWI5YWNcdWI5N2MgXHViOWNjXHViNGRjXHVjMmRjXHVjNjI0LiBcdWIyZTgsIFx1YWRmOFx1Yzc0MCBcdWMxMjBcdWJkODQgXHVjOTExIFx1YzViNFx1YjVhMFx1ZDU1YyBcdWI0NTAgXHVjMTIwXHViZDg0XHViM2M0IFx1YzExY1x1Yjg1YyBcdWFkNTBcdWNjMjhcdWQ1NThcdWJhNzQgXHVjNTQ4IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IFx1YzEyMFx1YmQ4NFx1Yzc1OCBcdWIwNWRcdWM4MTBcdWM3NzQgXHViMmU0XHViOTc4IFx1YzEyMFx1YmQ4NCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWFkNTBcdWNjMjhcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzc0XHViMmU0LiBcdWI0NTAgXHVjMTIwXHViZDg0XHVjNzc0IFx1YjA1ZFx1YzgxMFx1YzVkMFx1YzExYyBcdWI5Y2NcdWIwOThcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNTQ0XHViMmM4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCAkTiRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDIgXFxsZSBOIFxcbGUgMVxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwICROJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjhcdWM5MTEgJGkkXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAkaSRcdWJjODggXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1YyBcdWM4MTVcdWMyMTggJHhfaSQsICR5X2kkXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKC0xMF45IFxcbGUgeF9pLCB5X2kgXFxsZSAxMF45KSQ8XC9wPlxyXG5cclxuPHA+XHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YmFhOFx1YjRlMCBcdWM4MTBcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+JE4gLSAxJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWFkNmNcdWMxMzFcdWQ1NThcdWIyOTQgXHVjMTIwXHViZDg0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhYzAxIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMjBcdWJkODRcdWM3NDQgXHVjNzc0XHViOGU4XHViMjk0IFx1YjQ1MCBcdWM4MTBcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQyYjhcdWI5YWNcdWI5N2MgXHVhZTBiXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWM1ZWNcdWI3ZmZcdWM3NzggXHVhY2JkXHVjNmIwXHViMjk0IFx1YWRmOFx1YzkxMSBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVkNTU4XHViMDk4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjttYXgtd2lkdGg6NDAwcHg7IG1hcmdpbjogMCBhdXRvXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC85ZDUxYTA3Ni02YzA4LTQzOTItOWIxNC0xNzYwMTY4OGM3OGJcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwiaGVpZ2h0OiBhdXRvOyB3aWR0aDo0MDBweDtcIiBcLz48XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8yIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjttYXgtd2lkdGg6NDAwcHg7IG1hcmdpbjogMCBhdXRvXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9mNmEwM2RjZi03MTFiLTQzMWMtOTgyNy1iOGY4ZjI2ZTYyODRcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwiaGVpZ2h0OiBhdXRvOyB3aWR0aDogNDAwcHg7XCIgXC8+PFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjk3NTciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJEcmF3aW5nIGEgVHJlZSIsImRlc2NyaXB0aW9uIjoiPHA+T24gYSAyLWRpbWVuc2lvbmFsIHBsYW5lLCAkTiQgcG9pbnRzIGFyZSBnaXZlbi4gRHJhdyAkTi0xJCBsaW5lIHNlZ21lbnRzIHRvIGNyZWF0ZSBhIHRyZWUuIEhvd2V2ZXIsIG5vbmUgb2YgdGhlIGRyYXduIHNlZ21lbnRzIHNob3VsZCBpbnRlcnNlY3Qgd2l0aCBlYWNoIG90aGVyLjxcL3A+XHJcblxyXG48cD5JZiBhbiBlbmRwb2ludCBvZiBvbmUgc2VnbWVudCBsaWVzIG9uIGFub3RoZXIsIGl0IGlzIGNvbnNpZGVyZWQgYW4gaW50ZXJzZWN0aW9uLiBJZiB0d28gc2VnbWVudHMgbWVldCBvbmx5IGF0IHRoZWlyIGVuZHBvaW50cywgaXQmIzM5O3Mgbm90IGNvbnNpZGVyZWQgYW4gaW50ZXJzZWN0aW9uLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciAkTiQgcmVwcmVzZW50aW5nIHRoZSBudW1iZXIgb2YgcG9pbnRzLiAkKDIgXFxsZSBOIFxcbGUgMVxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPkZyb20gdGhlIHNlY29uZCBsaW5lIG9ud2FyZHMsIGZvciB0aGUgbmV4dCAkTiQgbGluZXMsIHRoZSBjb29yZGluYXRlcyBvZiB0aGUgcG9pbnRzIGFyZSBnaXZlbi4gT24gdGhlICRpJC10aCBsaW5lLCB0d28gaW50ZWdlcnMgJHhfaSRcdTIwMGIgYW5kICR5X2kkXHUyMDBiIHJlcHJlc2VudGluZyB0aGUgY29vcmRpbmF0ZXMgb2YgdGhlICRpJC10aCBwb2ludCBhcmUgZ2l2ZW4sIHNlcGFyYXRlZCBieSBhIHNwYWNlLiAkKC0xMF45IFxcbGUgeF9pLCB5X2kgXFxsZSAxMF45KSQ8XC9wPlxyXG5cclxuPHA+QWxsIGdpdmVuIHBvaW50cyBoYXZlIGRpc3RpbmN0IGNvb3JkaW5hdGVzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk92ZXIgJE4tMSQgbGluZXMsIG91dHB1dCB0aGUgbGluZSBzZWdtZW50cyB0aGF0IGNvbnN0cnVjdCZuYnNwO3RoZSB0cmVlLiBFYWNoIGxpbmUgc2hvdWxkIGNvbnRhaW4gdHdvIGludGVnZXJzIHJlcHJlc2VudGluZyB0aGUgaW5kaWNlcyBvZiB0aGUgcG9pbnRzIHRoYXQgZm9ybSBhIHNlZ21lbnQsIHNlcGFyYXRlZCBieSBhIHNwYWNlLjxcL3A+XHJcblxyXG48cD5JZiB0aGVyZSBhcmUgbXVsdGlwbGUgd2F5cyB0byBkcmF3IHRoZSB0cmVlLCB5b3UgY2FuIG91dHB1dCBhbnkgb2YgdGhlbS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvOWQ1MWEwNzYtNmMwOC00MzkyLTliMTQtMTc2MDE2ODhjNzhiXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cImhlaWdodDogMzk2cHg7IHdpZHRoOiA0MDBweDtcIiBcLz48XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8yIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9mNmEwM2RjZi03MTFiLTQzMWMtOTgyNy1iOGY4ZjI2ZTYyODRcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwiaGVpZ2h0OiAzOTVweDsgd2lkdGg6IDQwMHB4O1wiIFwvPjxcL3A+XHJcbiJ9XQ==