강아지 간식

가일동은 강아지 바두기와 함께 놀고 있다. 두 친구는 교차로 $n$개와 양방향 도로 $n-1$개가 있는 공원에 있다. 도로는 각각 길이가 $1$미터이고 교차로 두 개를 잇는다. 교차로는 $1$번부터 $n$번까지 번호가 붙어 있으며, 임의의 $a$, $b$ ($1\le a,b\le n$)에 대해 도로를 따라 $a$번 교차로에서 $b$번 교차로로 갈 수 있다.

가일동은 공원의 모든 교차로에 간식을 하나씩 놓았다. 그리고 바두기에게 간식을 모두 먹으라는 임무를 준다. 바두기는 $1$번 교차로에서 출발하고, 다음 규칙에 따라 움직인다.

• 바두기는 자기에게 가장 가까운 간식을 찾는다. 거리는 현재 위치에서 간식이 있는 교차로까지의 최단 경로 길이다. 그런데 바두기의 후각은 $k$미터까지만 닿으므로, 거리가 $k$ 이하인 간식만 찾을 수 있다. 그런 간식이 없으면 임무에 실패한다.
• 현재 위치에서 맡을 수 있는 간식 중, 이동해야 할 거리가 가장 짧은 간식을 고른다. 같은 거리의 간식이 여럿이면 그중 아무거나 고른다.
• 간식을 $n$개 모두 먹을 때까지 이 과정을 반복한다. 그 뒤에는 $1$번 교차로를 다시 찾아야 하며, 마지막으로 먹은 간식의 위치에서 $1$번 교차로까지의 거리도 $k$ 이하여야 한다. 찾으면 임무를 완료하고, 찾지 못하면 실패한다.

가일동은 $k$의 값을 모른다. 바두기가 최적으로 움직일 때 임무를 완료할 수 있는 $k$의 최솟값을 구하라.

첫 줄에 테스트 케이스의 개수 $t$ ($1\le t\le 10^4$)가 주어진다.

각 테스트 케이스의 첫 줄에는 교차로의 개수 $n$ ($2\le n\le 2\cdot 10^5$)이 주어진다.

이어지는 $n-1$개의 줄에는 정수 $u$와 $v$ ($1\le u,v\le n$, $u\ne v$)가 주어지며, 이는 교차로 $u$와 $v$ 사이에 도로가 있다는 뜻이다. 모든 도로는 양방향이며 서로 다르다.

각 테스트 케이스에서 임의의 $a$, $b$ ($1\le a,b\le n$)에 대해 도로를 따라 $a$번 교차로에서 $b$번 교차로로 갈 수 있는 것이 보장된다. 모든 테스트 케이스의 $n$의 합은 $2\cdot 10^5$를 넘지 않는다.

각 테스트 케이스마다 바두기가 임무를 완료할 수 있는 $k$의 최솟값을 한 줄에 출력한다.

첫 번째 경우, 바두기는 다음과 같이 움직여 $k=2$로 임무를 완료할 수 있다.

1. 바두기는 $1$번 교차로에 있다. 가장 가까운 간식은 $1$번 교차로에 있으므로 그것을 먹는다.
2. 다음으로 가까운 간식은 $2$번 또는 $3$번 교차로에 있다. $2$번 교차로를 골랐다고 하자. 바두기는 $1$미터를 이동해 $2$번 교차로의 간식을 먹는다.
3. 남은 간식은 $3$번 교차로에 하나뿐이고, 그곳까지 도로 두 개를 지나야 한다.
4. $3$번 교차로의 간식을 먹은 뒤, $1$미터 거리에 있는 $1$번 교차로를 다시 찾아간다. 이로써 임무를 완료한다.

두 번째 경우에 가능한 움직임은 $1 \to 2 \to 3 \to 4 \to 1$뿐이다. $4$번 교차로에서 $1$번 교차로까지의 거리는 $3$이므로, 임무를 완료하려면 $k$는 최소 $3$이어야 한다.

세 번째 경우 바두기는 $1 \to 5 \to 6 \to 7 \to 8 \to 2 \to 3 \to 4 \to 1$ 순서로 움직일 수 있다. $k=3$일 때 임무를 완료하는 움직임은 이것 하나뿐임을 보일 수 있다.