Given a tree, and the distance between two vertices is the minimum number of edges to traverse from one to the other. Then, the diameter of a tree is defined to be the maximum distance between any two vertices. Please find the diameter of the tree.
The diameter can be found by the following steps:
1. Pick any vertex v and perform BFS starting from v.
2. Let u be one of the vertex that is farthest away from v.
3. Perform BFS starting from u.
4. Let w be one of the vertex that is farthest away from u.
5. Output the distance between u and w as the answer.
The first line of input is an integer T (T <= 40) denoting the number of cases following.
For each case, the first line contains an integer N, denoting the number of nodes. Nodes are numbered from 1 to N. Then N-1 lines follows, each line contains two numbers of node which are connected by an edge.
Cases are separated by a blank line.
Problem size for the four testcases
1 < N < 10
1 < N < 100
1 < N < 1000
1 < N < 200000
For each case a line, output the diameter.