라우터 배치와 최대 TTL 최소화

대부분의 컴퓨터 네트워크는 트리 형태로 이루어져 있다. 즉, 어떤 컴퓨터와 다른 컴퓨터를 잇는 경로는 항상 정확히 하나뿐이다.

네트워크 패킷이 목적지에 도달하지 못하고 일정 시간이 지나면, 그 패킷은 버려진다. 이때 패킷이 살아 있는 시간을 TTL(Time To Live)이라고 한다. TTL이 없으면 패킷이 네트워크를 끝없이 돌게 되어 라우팅 테이블에 오류를 일으킬 수 있다.

한 대의 컴퓨터를 라우터로 정하면, 그 라우터에서 네트워크의 다른 모든 컴퓨터까지 통신하는 데 필요한 TTL(= 두 컴퓨터를 잇는 경로의 간선 수) 중 가장 큰 값이 그 라우터의 비용이 된다. 이 최대 TTL이 가장 작아지도록 라우터로 쓸 컴퓨터를 고르고 싶다.

네트워크가 주어졌을 때, 어떤 컴퓨터를 라우터로 사용하면 최대 TTL이 가장 작아지는지 구하고, 그때의 최대 TTL 값을 출력하는 프로그램을 작성하라.

첫째 줄에 테스트 케이스의 개수 $c$ ($1 \le c \le 100$)가 주어진다. 각 테스트 케이스의 첫째 줄에는 네트워크 안 컴퓨터의 개수 $N$ ($1 < N \le 100{,}000$)이 주어진다. 컴퓨터는 $0$번부터 $N-1$번까지 번호가 매겨져 있다. 이어지는 $N-1$개의 줄에는 서로 직접 연결된 두 컴퓨터의 번호 $a$와 $b$ ($0 \le a, b < N$)가 주어진다. $a$와 $b$가 연결되어 있으면 $b$와 $a$도 연결되어 있는 것으로 본다. 각 네트워크는 항상 트리를 이룬다.

각 테스트 케이스마다, 라우터로 쓸 컴퓨터를 가장 잘 골랐을 때의 최대 TTL 값(즉, 그 값을 최소화한 결과)을 한 줄에 하나씩 출력한다.