Tree Diameter

Given a tree with (n) nodes where node 1 is always considered the root, your task is to compute the diameter of the tree. The diameter is defined as the maximum distance between any two vertices in the tree, i.e., [ \text{Diameter} = \max_{u,v \in V} \text{dist}(u, v), ] where (\text{dist}(u, v)) represents the number of edges on the unique simple path between vertices (u) and (v).

You are given multiple test cases, and for each test case, you need to output the diameter of the corresponding tree on a separate line.

inputFormat

The input is given via standard input (stdin). The first line contains an integer (T) representing the number of test cases.

For each test case, the first line contains an integer (n), the number of nodes in the tree. It is followed by (n-1) lines, each containing two space-separated integers (u) and (v), indicating an edge between nodes (u) and (v).

outputFormat

For each test case, print a single integer on a new line representing the diameter of the tree. The output should be written to standard output (stdout).## sample

5
4
1 2
1 3
3 4
5
1 2
1 3
2 4
2 5
6
1 2
1 3
2 4
2 5
4 6
1
2
1 2

3
3
4
0
1