Description

Mr. Kuo is an adventurer. One day, he finds a maze.

The maze has N rooms. There may be a tunnel between rooms.

There is exactly one simple path between any two different rooms. That is, the maze is a "tree".

Mr. Kuo is curious about the length of the longest path in this maze. 

Take the sample test as the example：

• The longest path of the 1st test case is (2 → 1 → 3), whose length is 2.
• The longest path of the 2nd test case is (1 → 2 → 3), whose length is 2.
• The longest path of the 3rd test case is (5 → 7 → 3 → 1 → 4 → 2), whose length is 5.

 

[Hint] 

Instead of performing DFS twice, there is a solution to find the diameter in one DFS. For any tree whose root is \(i\), if we have two properties of its subtrees / children (\(j\)): the longest distance of the (sub-)tree (denoted by \(d\)) and the longest distance to any leaf (denoted by \(p\)). Then we have \(p_i=\displaystyle\max_{\forall j\text{ is a child of }i}(p_j+1)\), and \(d_i\) is either in its subtrees: \(\displaystyle\max_{\forall j\text{ is a child of }i}d_j\) or passing through the root: \(p_i+\displaystyle\max_{\forall j'\text{ is a child of }i}(p_{j'}+1)\), where \(j'\) mustn't be the same as we took in \(p_i\).

Input

The first line contains one integer T — the number of test cases. Description of the test cases follows.

The first line of each test case contains an integer N — the number of rooms in the maze.

Each of the next N - 1 line contains two integers u_i and v_i — there is a tunnel between u_i and v_i.

 

For each test：

1. T ≤ 10, N ≤ 10
2. T ≤ 10, N ≤ 100
3. T ≤ 10, N ≤ 500
4. T ≤ 10, N ≤ 1000
5. T ≤ 10, N ≤ 10000
6. T ≤ 30, N ≤ 20000

 

Output

For each test case print an integer — the length of the longest path in the maze.

Sample Input  Download

Sample Output  Download

Tags

Discuss