Time To Live

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

네트워크 패킷이 도착 장소까지 도착하지 못했을 때, 어떤 일정 시간이 지나면 그 패킷을 버린다. 이때, 이 시간을 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을 출력한다.