시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 104 26 21 38.889%

문제

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

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

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

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

입력

첫째 줄에 방의 개수 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+XHVjNWI0XHViMjkwXHViMGEwLCBcdWI0NTBcdWIzNTRcdWM5YzBcdWIyOTQgXHVjNWI0XHViNWE0IFx1YmMyOVx1YWNmYyBcdWM1YjRcdWI1YTQgXHViYzI5IFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI3N2MgXHViMTA4XHViYjM0IFx1YmE0MFx1YjJlNFx1YWNlMCBcdWMwZGRcdWFjMDFcdWQ1ODhcdWIyZTQuIFx1YjQ1MFx1YjM1NFx1YzljMFx1YjI5NCBcdWQxMzBcdWIxMTAgXHVkNTU4XHViMDk4XHViOTdjIFx1YjljOVx1YWNlMCwgXHVkMTMwXHViMTEwIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWMwYzhcdWI4NWMgXHVkMzBjXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWJhM2MgXHViNDUwIFx1YmMyOVx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVjZDVjXHVjMThjXHViODVjIFx1YjljY1x1YjRkY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViYWE4XHViNGUwIFx1YmMyOVx1Yzc0MCBcdWMxMWNcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDYwNFx1YzdhYyBcdWI0NTBcdWIzNTRcdWM5YzAgXHVjOWQxXHVjNzU4IFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWQxMzBcdWIxMTAgXHVkNTU4XHViMDk4XHViOTdjIFx1YjljOVx1YWNlMCwgXHVkNTU4XHViMDk4XHViOTdjIFx1YzBjOFx1Yjg1YyBcdWQzMGNcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YmEzYyBcdWI0NTAgXHViYzI5XHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWNkNWNcdWMxOGNcdWI4NWMgXHViOWNjXHViNGRjXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmMyOVx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmMyOVx1Yzc0MCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4IFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuICgzICZsZTsgTiAmbGU7IDMwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOLTFcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjQ1MCBcdWJjMjlcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1ZDEzMFx1YjExMFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjN2FjXHVhYzc0XHVjZDk1XHVjNzQ0IFx1ZDU1OFx1YWNlMFx1YjA5YyBcdWM3NzRcdWQ2YzRcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1YmEzYyBcdWI0NTAgXHVjOWQxXHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMmViXHVjNzQ0IFx1ZDEzMFx1YjExMFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBjOFx1Yjg1YyBcdWI5Y2NcdWI0ZTAgXHVkMTMwXHViMTEwXHVjNzU4IFx1YzgxNVx1YmNmNFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgxNVx1YjJmNVx1Yzc0MCBcdWM3MjBcdWM3N2NcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjdmMCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjk3MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktSVElDQSIsImRlc2NyaXB0aW9uIjoiPHA+TW9sZXMgYXJlIHRpZHkgYW5kIGhhcmQtd29ya2luZyBhbmltYWxzLiBPdXIgbW9sZSBsaWtlcyB0byBrZWVwIGl0cyB1bmRlcmdyb3VuZCByZXNpZGVuY2UgaW4gdXRtb3N0IG9yZGVyLCBzbyB0aGF0IGV2ZXJ5b25lIGxpdmluZyB0aGVyZSBrbm93cyB3aGVyZSB0byBmaW5kIHRoaW5ncy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VG8gYWNoaWV2ZSB0aGlzLCB0aGUgbW9sZSBjb25uZWN0ZWQgcm9vbXMgd2l0aCB0dW5uZWxzIHNvIHRoYXQgdGhlcmUgaXMgYSBzaW5nbGUgdW5pcXVlIHdheSB0byBnZXQgZnJvbSBvbmUgcm9vbSB0byBhbnkgb3RoZXIgcm9vbS4gVGhlIGRpc3RhbmNlIGJldHdlZW4gdHdvIHJvb21zIGlzIHRoZSBudW1iZXIgb2YgaGFsbHMgcGFzc2VkIG9uIHRoZSB3YXkgZnJvbSBvbmUgdG8gdGhlIG90aGVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5EZXNwaXRlIGFsbCB0aGUgZWZmb3J0LCBzb21lIG9mIHRoZSBtb2xlJiMzOTtzIGd1ZXN0cyBhcmUgY29tcGxhaW5pbmcgdGhhdCBpdCB0YWtlcyB0b28gbG9uZyB0byB3YWxrIGJldHdlZW4gY2VydGFpbiBwYWlycyBvZiByb29tcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG1vbGUgZGVjaWRlZCB0byByZWNvbnN0cnVjdCBoZXIgcmVzaWRlbmNlLCBjbG9zaW5nIG9uZSB0dW5uZWwgYW5kIG9wZW5pbmcgYSBuZXcgb25lLCBzbyB0aGF0IHRoZSBkaXN0YW5jZSBiZXR3ZWVuIHRoZSBmYXJ0aGVzdCB0d28gcm9vbXMgaXMgdGhlIHNtYWxsZXN0IHBvc3NpYmxlLCBidXQgc28gdGhhdCBpdCBpcyBzdGlsbCBwb3NzaWJsZSB0byByZWFjaCBldmVyeSByb29tIGZyb20gZXZlcnkgb3RoZXIgcm9vbS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHdoaWNoIGRldGVybWluZXMgdGhlIGRpc3RhbmNlIGJldHdlZW4gdGhlIGZhcnRoZXN0IHR3byByb29tcyBhZnRlciByZWNvbnN0cnVjdGlvbiwgd2hpY2ggdHVubmVsIHRvIGNsb3NlIGFuZCB3aGljaCB0byBvcGVuLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDMwMCAwMDApLCB0aGUgbnVtYmVyIG9mIHJvb21zLiBUaGUgcm9vbXMgYXJlIG51bWJlcmVkIDEgdG8gTi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCBOJm1pbnVzOzEgbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzLCB0aGUgbnVtYmVycyBvZiByb29tcyBhIHR1bm5lbCBjb25uZWN0cy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgb24gc2VwYXJhdGUgbGluZXMsIGluIG9yZGVyOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlRoZSBkaXN0YW5jZSBiZXR3ZWVuIHRoZSB0d28gZmFydGhlc3Qgcm9vbXMgYWZ0ZXIgcmVjb25zdHJ1Y3Rpb24uJm5ic3A7PFwvbGk+XHJcblx0PGxpPkEgcGFpciBvZiBpbnRlZ2VycyByZXByZXNlbnRpbmcgYSBwcmV2aW91c2x5IGV4aXN0aW5nIHR1bm5lbCwgd2hpY2ggc2hvdWxkIGJlIGNsb3NlZC4mbmJzcDs8XC9saT5cclxuXHQ8bGk+QSBwYWlyIG9mIGludGVnZXJzLCB0aGUgcm9vbXMgYmV0d2VlbiB3aGljaCBhIG5ldyB0dW5uZWwgc2hvdWxkIGJlIG9wZW5lZC4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Ob3RlOiBUaGUgc29sdXRpb24gd2lsbCBub3QgbmVjZXNzYXJpbHkgYmUgdW5pcXVlLiBPdXRwdXQgYW55IHJlY29uc3RydWN0aW9uIHBsYW4gd2hpY2ggYWNoaWV2ZXMgdGhlIHNtYWxsZXN0IGRpc3RhbmNlIGJldHdlZW4gdGhlIGZhcnRoZXN0IHR3byByb29tcy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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