시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 65 16 11 37.931%

문제

대부분의 컴퓨터 네트워크는 트리 형태로 이루어져 있다. 즉, 각 컴퓨터와 다른 컴퓨터 사이의 경로는 항상 하나이다.

네트워크 패킷이 도착 장소까지 도착하지 못했을 때, 어떤 일정 시간이 지나면 그 패킷을 버린다. 이때, 이 시간을 Time to live(TTL)이라고 한다. TTL이 없다면, 패킷이 네트워크를 계속해서 순환하게 되고, 이는 라우팅 테이블의 에러를 일으킬 수 있기 때문이다.

라우터와 같은 네트워크 안의 다른 컴퓨터와 통신하는데 필요한 TTL의 최댓값이 가장 작게 라우터를 배치할 수 있다. 이렇게 네트워크와 다른 네트워크를 연결하는 라우터를 배치하면 최적의 방법으로 라우터를 배치할 수 있다.

위에서 설명한 네트워크가 주어졌을 때, 어떤 컴퓨터를 라우터로 사용해야 최대 TTL값이 가장 작아지는 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 c(1 ≤ c ≤ 100)가 주어진다. 각 테스트 케이스의 첫째 줄에는 네트워크 안의 컴퓨터의 개수 N(1 < N ≤ 100,000)이 주어진다. 컴퓨터는 0번부터 N-1번까지 번호가 매겨져 있다. 다음 N-1줄에는 서로 연결되어 있는 컴퓨터의 번호 a와 b가 주어진다. (0 ≤ a,b < N) a와 b가 연결되어 있다면, b와 a도 연결되어 있는 것이다.

출력

이 네트워크에 라우터를 설치한다면, 어느 컴퓨터를 라우터로 사용해야 가장 큰 TTL 값이 작아지는지를 구한 뒤, TTL을 출력한다.

예제 입력 1

3
2
1 0
5
3 2
2 1
0 2
2 4
9
3 1
6 5
3 4
0 3
8 1
1 7
1 6
2 3

예제 출력 1

1
1
2
W3sicHJvYmxlbV9pZCI6IjM5NzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJUaW1lIFRvIExpdmUiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YjMwMFx1YmQ4MFx1YmQ4NFx1Yzc1OCBcdWNlZjRcdWQ0ZThcdWQxMzAgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjXHViMjk0IFx1ZDJiOFx1YjlhYyBcdWQ2MTVcdWQwZGNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjOTg5LCBcdWFjMDEgXHVjZWY0XHVkNGU4XHVkMTMwXHVjNjQwIFx1YjJlNFx1Yjk3OCBcdWNlZjRcdWQ0ZThcdWQxMzAgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWNiZFx1Yjg1Y1x1YjI5NCBcdWQ1NmRcdWMwYzEgXHVkNTU4XHViMDk4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmMgXHVkMzI4XHVkMGI3XHVjNzc0IFx1YjNjNFx1Y2MyOSBcdWM3YTVcdWMxOGNcdWFlNGNcdWM5YzAgXHViM2M0XHVjYzI5XHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YzViNFx1YjVhNCBcdWM3N2NcdWM4MTUgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YzljMFx1YjA5OFx1YmE3NCBcdWFkZjggXHVkMzI4XHVkMGI3XHVjNzQ0IFx1YmM4NFx1YjliMFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWM3NzQgXHVjMmRjXHVhYzA0XHVjNzQ0IFRpbWUgdG8gbGl2ZShUVEwpXHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC4gVFRMXHVjNzc0IFx1YzVjNlx1YjJlNFx1YmE3NCwgXHVkMzI4XHVkMGI3XHVjNzc0IFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2Y1x1Yjk3YyBcdWFjYzRcdWMxOGRcdWQ1NzRcdWMxMWMgXHVjMjFjXHVkNjU4XHVkNTU4XHVhYzhjIFx1YjQxOFx1YWNlMCwgXHVjNzc0XHViMjk0IFx1Yjc3Y1x1YzZiMFx1ZDMwNSBcdWQxNGNcdWM3NzRcdWJlMTRcdWM3NTggXHVjNWQwXHViN2VjXHViOTdjIFx1Yzc3Y1x1YzczY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViNzdjXHVjNmIwXHVkMTMwXHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmMgXHVjNTQ4XHVjNzU4IFx1YjJlNFx1Yjk3OCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWM2NDAgXHVkMWI1XHVjMmUwXHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBUVExcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzc0IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWFjOGMgXHViNzdjXHVjNmIwXHVkMTMwXHViOTdjIFx1YmMzMFx1Y2U1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjXHVjNjQwIFx1YjJlNFx1Yjk3OCBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmNcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1Yjc3Y1x1YzZiMFx1ZDEzMFx1Yjk3YyBcdWJjMzBcdWNlNThcdWQ1NThcdWJhNzQgXHVjZDVjXHVjODAxXHVjNzU4IFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWI3N2NcdWM2YjBcdWQxMzBcdWI5N2MgXHViYzMwXHVjZTU4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzcwNFx1YzVkMFx1YzExYyBcdWMxMjRcdWJhODVcdWQ1NWMgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzViNFx1YjVhNCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWI5N2MgXHViNzdjXHVjNmIwXHVkMTMwXHViODVjIFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzU3YyBcdWNkNWNcdWIzMDAgVFRMXHVhYzEyXHVjNzc0IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM1NDRcdWM5YzBcdWIyOTQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IGMoMSAmbGU7IGMgJmxlOyAxMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmMgXHVjNTQ4XHVjNzU4IFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1Yzc1OCBcdWFjMWNcdWMyMTggTigxICZsdDsgTiAmbGU7IDEwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjZWY0XHVkNGU4XHVkMTMwXHViMjk0IDBcdWJjODhcdWJkODBcdWQxMzAgTi0xXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiBcdWIyZTRcdWM3NGMgTi0xXHVjOTA0XHVjNWQwXHViMjk0IFx1YzExY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1Yzc1OCBcdWJjODhcdWQ2MzggYVx1YzY0MCBiXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyBhLGIgJmx0OyBOKSBhXHVjNjQwIGJcdWFjMDAgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNFx1YmE3NCwgYlx1YzY0MCBhXHViM2M0IFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Yzc3NCBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmNcdWM1ZDAgXHViNzdjXHVjNmIwXHVkMTMwXHViOTdjIFx1YzEyNFx1Y2U1OFx1ZDU1Y1x1YjJlNFx1YmE3NCwgXHVjNWI0XHViMjkwIFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1Yjk3YyBcdWI3N2NcdWM2YjBcdWQxMzBcdWI4NWMgXHVjMGFjXHVjNmE5XHVkNTc0XHVjNTdjIFx1YWMwMFx1YzdhNSBcdWQwNzAgVFRMIFx1YWMxMlx1Yzc3NCBcdWM3OTFcdWM1NDRcdWM5YzBcdWIyOTRcdWM5YzBcdWI5N2MgXHVhZDZjXHVkNTVjIFx1YjRhNCwgVFRMXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzOTczIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGltZSB0byBsaXZlIiwiZGVzY3JpcHRpb24iOiI8cD5BcyB5b3UgbWlnaHQga25vdywgbW9zdCBjb21wdXRlciBuZXR3b3JrcyBhcmUgb3JnYW5pemVkIGluIGEgdHJlZS1saWtlIGZhc2hpb24sIGkuZS4gZWFjaCBjb21wdXRlciBpcyByZWFjaGFibGUgYnkgZWFjaCBvdGhlciBjb21wdXRlciBidXQgb25seSBvdmVyIG9uZSwgdW5pcXVlIHBhdGguPFwvcD5cclxuXHJcbjxwPlRoZSBzby1jYWxsZWQgVGltZSB0byBsaXZlIChUVEwpIHNwZWNpZmllcyBhZnRlciBob3cgbWFueSBob3BzIGEgbmV0d29yayBwYWNrZXQgaXMgZHJvcHBlZCBpZiBpdCBoYXMgbm90IHJlYWNoZWQgaXRzIGRlc3RpbmF0aW9uIHlldC4gVGhlIHB1cnBvc2Ugb2YgdGhlIFRUTCBpcyB0byBhdm9pZCBzaXR1YXRpb25zIGluIHdoaWNoIGEgcGFja2V0IGNpcmN1bGF0ZXMgdGhyb3VnaCB0aGUgbmV0d29yayBjYXVzZWQgYnkgZXJyb3JzIGluIHRoZSByb3V0aW5nIHRhYmxlcy48XC9wPlxyXG5cclxuPHA+VGhlIHBsYWNlbWVudCBvZiBhIHJvdXRlciB0aGF0IGNvbm5lY3RzIHRoZSBuZXR3b3JrIHRvIGFub3RoZXIgbmV0d29yayBpcyBvcHRpbWFsIHdoZW4gdGhlIG1heGltYWwgbmVlZGVkIFRUTCBmb3IgcGFja2V0cyB0aGF0IGFyZSBzZW50IGZyb20gdGhpcyByb3V0ZXIgdG8gYW55IG90aGVyIGNvbXB1dGVyIHdpdGhpbiB0aGUgc2FtZSBuZXR3b3JrIGlzIG1pbmltYWwuIEdpdmVuIGEgbmV0d29yayBhcyBzcGVjaWZpZWQgYWJvdmUsIHlvdSBzaG91bGQgY2FsY3VsYXRlIHRoZSBtYXhpbWFsIG5lZWRlZCBUVEwgaW4gdGhpcyBuZXR3b3JrIGlmIHlvdSBjYW4gc2VsZWN0IHRoZSBjb21wdXRlciB0aGF0IHNob3VsZCBiZSB1c2VkIGFzIHJvdXRlci48XC9wPiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnNpc3RzIG9mIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBjIHRoYXQgZm9sbG93ICgxICZsZTsgYyAmbGU7IDEwMCkuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGEgbGluZSBzcGVjaWZ5aW5nIE4sIHRoZSBudW1iZXIgb2YgY29tcHV0ZXJzIGluIHRoaXMgbmV0d29yayAoMSAmbHQ7IE4gJmxlOyZuYnNwOzEwMCAwMDApLiBDb21wdXRlcnMgYXJlIG51bWJlcmVkIGZyb20gMCB0byBOIC0gMS4gVGhlbiBmb2xsb3cgTiAtIDEgbGluZXMsIGVhY2ggc3BlY2lmeWluZyBhIG5ldHdvcmsgY29ubmVjdGlvbiBieSB0d28gbnVtYmVycyBhIGFuZCBiIHdoaWNoIG1lYW5zIHRoYXQgY29tcHV0ZXIgYSBpcyBjb25uZWN0ZWQgdG8gY29tcHV0ZXIgYiBhbmQgdmljZSB2ZXJzYSwgb2YgY291cnNlICgwICZsZTsmbmJzcDthLCBiICZsdDsgTikuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIGluIHRoZSBpbnB1dCwgcHJpbnQgb25lIGxpbmUgY29udGFpbmluZyB0aGUgb3B0aW1hbCBUVEwgYXMgc3BlY2lmaWVkIGFib3ZlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==