시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 94 23 18 40.909%

문제

두더지는 땅에 터널을 파고 생활하는 동물이다. 땅속에 있는 두더지의 집은 방과 터널로 이루어져 있다.

방은 터널로 연결되어 있으며, 한 방에서 다른 방으로 가는 경로는 항상 유일하다. 두 방의 거리는 지나간 터널의 수와 같다.

어느날, 두더지는 어떤 방과 어떤 방 사이의 거리라 너무 멀다고 생각했다. 두더지는 터널 하나를 막고, 터널 하나를 새로 파서 가장 먼 두 방의 거리를 최소로 만드려고 한다. 이 때, 모든 방은 서로 연결되어 있어야 한다.

현재 두더지 집의 상태가 주어졌을 때, 터널 하나를 막고, 하나를 새로 파서 가장 먼 두 방의 거리를 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 방의 개수 N이 주어진다. 방은 1번부터 N번까지 번호 매겨져 있다. (3 ≤ N ≤ 300,000)

다음 N-1개 줄에는 두 방을 연결하는 터널의 정보가 주어진다.

출력

첫째 줄에 재건축을 하고난 이후에 가장 먼 두 집의 거리를 출력한다.

둘째 줄에는 닫을 터널의 정보를 출력한다.

셋째 줄에는 새로 만든 터널의 정보를 출력한다.

정답은 유일하지 않을 수 있다. 이런 경우에는 아무거나 출력하면 된다. 

예제 입력 1

4
1 2
2 3
3 4

예제 출력 1

2
3 4
4 2
W3sicHJvYmxlbV9pZCI6IjI5NzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI0NTBcdWIzNTRcdWM5YzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjQ1MFx1YjM1NFx1YzljMFx1YjI5NCBcdWI1NDVcdWM1ZDAgXHVkMTMwXHViMTEwXHVjNzQ0IFx1ZDMwY1x1YWNlMCBcdWMwZGRcdWQ2NWNcdWQ1NThcdWIyOTQgXHViM2Q5XHViYjNjXHVjNzc0XHViMmU0LiBcdWI1NDVcdWMxOGRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjQ1MFx1YjM1NFx1YzljMFx1Yzc1OCBcdWM5ZDFcdWM3NDAgXHViYzI5XHVhY2ZjIFx1ZDEzMFx1YjExMFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjMjlcdWM3NDAgXHVkMTMwXHViMTEwXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1ZDU1YyBcdWJjMjlcdWM1ZDBcdWMxMWMgXHViMmU0XHViOTc4IFx1YmMyOVx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHVhY2JkXHViODVjXHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWM3MjBcdWM3N2NcdWQ1NThcdWIyZTQuIFx1YjQ1MCBcdWJjMjlcdWM3NTggXHVhYzcwXHViOWFjXHViMjk0IFx1YzljMFx1YjA5OFx1YWMwNCBcdWQxMzBcdWIxMTBcdWM3NTggXHVjMjE4XHVjNjQwIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViMjkwXHViMGEwLCBcdWI0NTBcdWIzNTRcdWM5YzBcdWIyOTQgXHVjNWI0XHViNWE0IFx1YmMyOVx1YWNmYyBcdWM1YjRcdWI1YTQgXHViYzI5IFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI3N2MgXHViMTA4XHViYjM0IFx1YmE0MFx1YjJlNFx1YWNlMCBcdWMwZGRcdWFjMDFcdWQ1ODhcdWIyZTQuIFx1YjQ1MFx1YjM1NFx1YzljMFx1YjI5NCBcdWQxMzBcdWIxMTAgXHVkNTU4XHViMDk4XHViOTdjIFx1YjljOVx1YWNlMCwgXHVkMTMwXHViMTEwIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWMwYzhcdWI4NWMgXHVkMzBjXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWJhM2MgXHViNDUwIFx1YmMyOVx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVjZDVjXHVjMThjXHViODVjIFx1YjljY1x1YjRkY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YmFhOFx1YjRlMCBcdWJjMjlcdWM3NDAgXHVjMTFjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ2MDRcdWM3YWMgXHViNDUwXHViMzU0XHVjOWMwIFx1YzlkMVx1Yzc1OCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkMTMwXHViMTEwIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWI5YzlcdWFjZTAsIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWMwYzhcdWI4NWMgXHVkMzBjXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWJhM2MgXHViNDUwIFx1YmMyOVx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVjZDVjXHVjMThjXHViODVjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjMjlcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJjMjlcdWM3NDAgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiAoMyAmbGU7IE4gJmxlOyAzMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTi0xXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI0NTAgXHViYzI5XHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWQxMzBcdWIxMTBcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzdhY1x1YWM3NFx1Y2Q5NVx1Yzc0NCBcdWQ1NThcdWFjZTBcdWIwOWMgXHVjNzc0XHVkNmM0XHVjNWQwIFx1YWMwMFx1YzdhNSBcdWJhM2MgXHViNDUwIFx1YzlkMVx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjJlYlx1Yzc0NCBcdWQxMzBcdWIxMTBcdWM3NTggXHVjODE1XHViY2Y0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYzhcdWI4NWMgXHViOWNjXHViNGUwIFx1ZDEzMFx1YjExMFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWIyZjVcdWM3NDAgXHVjNzIwXHVjNzdjXHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI3ZjAgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzU0NFx1YmIzNFx1YWM3MFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI5NzAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJLUlRJQ0EiLCJkZXNjcmlwdGlvbiI6IjxwPk1vbGVzIGFyZSB0aWR5IGFuZCBoYXJkLXdvcmtpbmcgYW5pbWFscy4gT3VyIG1vbGUgbGlrZXMgdG8ga2VlcCBpdHMgdW5kZXJncm91bmQgcmVzaWRlbmNlIGluIHV0bW9zdCBvcmRlciwgc28gdGhhdCBldmVyeW9uZSBsaXZpbmcgdGhlcmUga25vd3Mgd2hlcmUgdG8gZmluZCB0aGluZ3MuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRvIGFjaGlldmUgdGhpcywgdGhlIG1vbGUgY29ubmVjdGVkIHJvb21zIHdpdGggdHVubmVscyBzbyB0aGF0IHRoZXJlIGlzIGEgc2luZ2xlIHVuaXF1ZSB3YXkgdG8gZ2V0IGZyb20gb25lIHJvb20gdG8gYW55IG90aGVyIHJvb20uIFRoZSBkaXN0YW5jZSBiZXR3ZWVuIHR3byByb29tcyBpcyB0aGUgbnVtYmVyIG9mIGhhbGxzIHBhc3NlZCBvbiB0aGUgd2F5IGZyb20gb25lIHRvIHRoZSBvdGhlci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RGVzcGl0ZSBhbGwgdGhlIGVmZm9ydCwgc29tZSBvZiB0aGUgbW9sZSYjMzk7cyBndWVzdHMgYXJlIGNvbXBsYWluaW5nIHRoYXQgaXQgdGFrZXMgdG9vIGxvbmcgdG8gd2FsayBiZXR3ZWVuIGNlcnRhaW4gcGFpcnMgb2Ygcm9vbXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBtb2xlIGRlY2lkZWQgdG8gcmVjb25zdHJ1Y3QgaGVyIHJlc2lkZW5jZSwgY2xvc2luZyBvbmUgdHVubmVsIGFuZCBvcGVuaW5nIGEgbmV3IG9uZSwgc28gdGhhdCB0aGUgZGlzdGFuY2UgYmV0d2VlbiB0aGUgZmFydGhlc3QgdHdvIHJvb21zIGlzIHRoZSBzbWFsbGVzdCBwb3NzaWJsZSwgYnV0IHNvIHRoYXQgaXQgaXMgc3RpbGwgcG9zc2libGUgdG8gcmVhY2ggZXZlcnkgcm9vbSBmcm9tIGV2ZXJ5IG90aGVyIHJvb20uJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaCBkZXRlcm1pbmVzIHRoZSBkaXN0YW5jZSBiZXR3ZWVuIHRoZSBmYXJ0aGVzdCB0d28gcm9vbXMgYWZ0ZXIgcmVjb25zdHJ1Y3Rpb24sIHdoaWNoIHR1bm5lbCB0byBjbG9zZSBhbmQgd2hpY2ggdG8gb3Blbi4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAzMDAgMDAwKSwgdGhlIG51bWJlciBvZiByb29tcy4gVGhlIHJvb21zIGFyZSBudW1iZXJlZCAxIHRvIE4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIG5leHQgTiZtaW51czsxIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycywgdGhlIG51bWJlcnMgb2Ygcm9vbXMgYSB0dW5uZWwgY29ubmVjdHMuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IG9uIHNlcGFyYXRlIGxpbmVzLCBpbiBvcmRlcjombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgZGlzdGFuY2UgYmV0d2VlbiB0aGUgdHdvIGZhcnRoZXN0IHJvb21zIGFmdGVyIHJlY29uc3RydWN0aW9uLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5BIHBhaXIgb2YgaW50ZWdlcnMgcmVwcmVzZW50aW5nIGEgcHJldmlvdXNseSBleGlzdGluZyB0dW5uZWwsIHdoaWNoIHNob3VsZCBiZSBjbG9zZWQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPkEgcGFpciBvZiBpbnRlZ2VycywgdGhlIHJvb21zIGJldHdlZW4gd2hpY2ggYSBuZXcgdHVubmVsIHNob3VsZCBiZSBvcGVuZWQuJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Tm90ZTogVGhlIHNvbHV0aW9uIHdpbGwgbm90IG5lY2Vzc2FyaWx5IGJlIHVuaXF1ZS4gT3V0cHV0IGFueSByZWNvbnN0cnVjdGlvbiBwbGFuIHdoaWNoIGFjaGlldmVzIHRoZSBzbWFsbGVzdCBkaXN0YW5jZSBiZXR3ZWVuIHRoZSBmYXJ0aGVzdCB0d28gcm9vbXMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #1 6번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: khsoo01