시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 44 9 8 42.105%

문제

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

네트워크 패킷이 도착 장소까지 도착하지 못했을 때, 어떤 일정 시간이 지나면 그 패킷을 버린다. 이 때, 이 시간을 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+XHJcblxyXG48cD5cclxuXHRcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmMgXHVkMzI4XHVkMGI3XHVjNzc0IFx1YjNjNFx1Y2MyOSBcdWM3YTVcdWMxOGNcdWFlNGNcdWM5YzAgXHViM2M0XHVjYzI5XHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YzViNFx1YjVhNCBcdWM3N2NcdWM4MTUgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YzljMFx1YjA5OFx1YmE3NCBcdWFkZjggXHVkMzI4XHVkMGI3XHVjNzQ0IFx1YmM4NFx1YjliMFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVjNzc0IFx1YzJkY1x1YWMwNFx1Yzc0NCBUaW1lIHRvIGxpdmUoVFRMKVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFRUTFx1Yzc3NCBcdWM1YzZcdWIyZTRcdWJhNzQsIFx1ZDMyOFx1ZDBiN1x1Yzc3NCBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmNcdWI5N2MgXHVhY2M0XHVjMThkXHVkNTc0XHVjMTFjIFx1YzIxY1x1ZDY1OFx1ZDU1OFx1YWM4YyBcdWI0MThcdWFjZTAsIFx1Yzc3NFx1YjI5NCBcdWI3N2NcdWM2YjBcdWQzMDUgXHVkMTRjXHVjNzc0XHViZTE0XHVjNzU4IFx1YzVkMFx1YjdlY1x1Yjk3YyBcdWM3N2NcdWM3M2NcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yjc3Y1x1YzZiMFx1ZDEzMFx1YzY0MCBcdWFjMTlcdWM3NDAgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjIFx1YzU0OFx1Yzc1OCBcdWIyZTRcdWI5NzggXHVjZWY0XHVkNGU4XHVkMTMwXHVjNjQwIFx1ZDFiNVx1YzJlMFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgVFRMXHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWMxMlx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVhYzhjIFx1Yjc3Y1x1YzZiMFx1ZDEzMFx1Yjk3YyBcdWJjMzBcdWNlNThcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViODA3XHVhYzhjIFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2Y1x1YzY0MCBcdWIyZTRcdWI5NzggXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWI3N2NcdWM2YjBcdWQxMzBcdWI5N2MgXHViYzMwXHVjZTU4XHVkNTU4XHViYTc0IFx1Y2Q1Y1x1YzgwMVx1Yzc1OCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHViNzdjXHVjNmIwXHVkMTMwXHViOTdjIFx1YmMzMFx1Y2U1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3MDRcdWM1ZDBcdWMxMWMgXHVjMTI0XHViYTg1XHVkNTVjIFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM1YjRcdWI1YTQgXHVjZWY0XHVkNGU4XHVkMTMwXHViOTdjIFx1Yjc3Y1x1YzZiMFx1ZDEzMFx1Yjg1YyBcdWMwYWNcdWM2YTlcdWQ1NzRcdWM1N2MgXHVjZDVjXHViMzAwIFRUTFx1YWMxMlx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNTQ0XHVjOWMwXHViMjk0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBjKDEgJmxlOyBjICZsZTsgMTAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjIFx1YzU0OFx1Yzc1OCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWM3NTggXHVhYzFjXHVjMjE4IE4oMSAmbHQ7IE4gJmxlOyAxMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1YjI5NCAwXHViYzg4XHViZDgwXHVkMTMwIE4tMVx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViMmU0XHVjNzRjIE4tMVx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMWNcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWM3NTggXHViYzg4XHVkNjM4IGFcdWM2NDAgYlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgYSxiICZsdDsgTikgYVx1YzY0MCBiXHVhYzAwIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTRcdWJhNzQsIGJcdWM2NDAgYVx1YjNjNCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWM3NzQgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjXHVjNWQwIFx1Yjc3Y1x1YzZiMFx1ZDEzMFx1Yjk3YyBcdWMxMjRcdWNlNThcdWQ1NWNcdWIyZTRcdWJhNzQsIFx1YzViNFx1YjI5MCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWI5N2MgXHViNzdjXHVjNmIwXHVkMTMwXHViODVjIFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzU3YyBcdWFjMDBcdWM3YTUgXHVkMDcwIFRUTCBcdWFjMTJcdWM3NzQgXHVjNzkxXHVjNTQ0XHVjOWMwXHViMjk0XHVjOWMwXHViOTdjIFx1YWQ2Y1x1ZDU1YyBcdWI0YTQsIFRUTFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzk3MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRpbWUgdG8gbGl2ZSIsImRlc2NyaXB0aW9uIjoiPHA+QXMgeW91IG1pZ2h0IGtub3csIG1vc3QgY29tcHV0ZXIgbmV0d29ya3MgYXJlIG9yZ2FuaXplZCBpbiBhIHRyZWUtbGlrZSBmYXNoaW9uLCBpLmUuIGVhY2ggY29tcHV0ZXIgaXMgcmVhY2hhYmxlIGJ5IGVhY2ggb3RoZXIgY29tcHV0ZXIgYnV0IG9ubHkgb3ZlciBvbmUsIHVuaXF1ZSBwYXRoLjxcL3A+XHJcblxyXG48cD5UaGUgc28tY2FsbGVkIFRpbWUgdG8gbGl2ZSAoVFRMKSBzcGVjaWZpZXMgYWZ0ZXIgaG93IG1hbnkgaG9wcyBhIG5ldHdvcmsgcGFja2V0IGlzIGRyb3BwZWQgaWYgaXQgaGFzIG5vdCByZWFjaGVkIGl0cyBkZXN0aW5hdGlvbiB5ZXQuIFRoZSBwdXJwb3NlIG9mIHRoZSBUVEwgaXMgdG8gYXZvaWQgc2l0dWF0aW9ucyBpbiB3aGljaCBhIHBhY2tldCBjaXJjdWxhdGVzIHRocm91Z2ggdGhlIG5ldHdvcmsgY2F1c2VkIGJ5IGVycm9ycyBpbiB0aGUgcm91dGluZyB0YWJsZXMuPFwvcD5cclxuXHJcbjxwPlRoZSBwbGFjZW1lbnQgb2YgYSByb3V0ZXIgdGhhdCBjb25uZWN0cyB0aGUgbmV0d29yayB0byBhbm90aGVyIG5ldHdvcmsgaXMgb3B0aW1hbCB3aGVuIHRoZSBtYXhpbWFsIG5lZWRlZCBUVEwgZm9yIHBhY2tldHMgdGhhdCBhcmUgc2VudCBmcm9tIHRoaXMgcm91dGVyIHRvIGFueSBvdGhlciBjb21wdXRlciB3aXRoaW4gdGhlIHNhbWUgbmV0d29yayBpcyBtaW5pbWFsLiBHaXZlbiBhIG5ldHdvcmsgYXMgc3BlY2lmaWVkIGFib3ZlLCB5b3Ugc2hvdWxkIGNhbGN1bGF0ZSB0aGUgbWF4aW1hbCBuZWVkZWQgVFRMIGluIHRoaXMgbmV0d29yayBpZiB5b3UgY2FuIHNlbGVjdCB0aGUgY29tcHV0ZXIgdGhhdCBzaG91bGQgYmUgdXNlZCBhcyByb3V0ZXIuPFwvcD4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb25zaXN0cyBvZiB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgYyB0aGF0IGZvbGxvdyAoMSAmbGU7IGMgJmxlOyAxMDApLiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgc3BlY2lmeWluZyBOLCB0aGUgbnVtYmVyIG9mIGNvbXB1dGVycyBpbiB0aGlzIG5ldHdvcmsgKDEgJmx0OyBOICZsZTsmbmJzcDsxMDAgMDAwKS4gQ29tcHV0ZXJzIGFyZSBudW1iZXJlZCBmcm9tIDAgdG8gTiAtIDEuIFRoZW4gZm9sbG93IE4gLSAxIGxpbmVzLCBlYWNoIHNwZWNpZnlpbmcgYSBuZXR3b3JrIGNvbm5lY3Rpb24gYnkgdHdvIG51bWJlcnMgYSBhbmQgYiB3aGljaCBtZWFucyB0aGF0IGNvbXB1dGVyIGEgaXMgY29ubmVjdGVkIHRvIGNvbXB1dGVyIGIgYW5kIHZpY2UgdmVyc2EsIG9mIGNvdXJzZSAoMCAmbGU7Jm5ic3A7YSwgYiAmbHQ7IE4pLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBpbiB0aGUgaW5wdXQsIHByaW50IG9uZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG9wdGltYWwgVFRMIGFzIHNwZWNpZmllZCBhYm92ZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=