JAG 반격

JAG는 회사 $BEST$가 새로 만든 혁명적인 게임이다. 이 게임은 $T$ 라운드로 진행되며, 각 라운드마다 플레이어는 $N$개의 영역으로 이루어진 지도를 받는다. 지도에서 국경을 맞대고 있는 영역의 쌍은 정확히 $N-1$개이고, 지도는 연결되어 있다. 즉 임의의 두 영역 $u$와 $v$에 대해, 다른 영역을 거쳐서라도 $u$에서 $v$로 이동할 수 있다.

플레이어들은 모든 영역이 선택될 때까지 번갈아 영역을 고른다. 규칙은 두 가지다.

• 차례를 건너뛸 수 없다.
• 플레이어는 자신이나 상대가 이미 선택한 영역을 다시 고를 수 없다.

두 영역 $u$와 $v$의 거리는 $u$에서 $v$로 가는 경로 중 넘어야 하는 국경의 최소 개수이다. 첫 번째 플레이어는 자신이 고른 영역 중 가장 먼 두 영역 사이의 거리를 최소로 만들려고 한다. 두 번째 플레이어는 그 거리를 최대로 만들려고 한다. 두 플레이어가 최적으로 플레이할 때, 첫 번째 플레이어가 고른 영역 중 가장 먼 두 영역 사이의 거리를 출력하라.

첫 줄에 라운드 수 $T$가 주어진다. 각 라운드의 첫 줄에는 영역의 개수 $N$ ($3 \leq N \leq 10^5$)이 주어진다. 이어지는 $N-1$개의 줄에는 국경을 맞대고 있는 두 영역 $u$와 $v$가 주어진다. 모든 라운드의 $N$을 합하면 200000을 넘지 않는다.

$T$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 라운드의 답을 출력한다.