Tree Diameter

You are given one or more trees. For each tree, your task is to determine its diameter, which is defined as the length of the longest simple path in the tree. In other words, if the tree has n nodes, the diameter is the maximum distance between any two nodes.

Recall that for a tree, a path is a sequence of vertices where each adjacent pair is connected by an edge and no vertex is repeated.

You can use the following property: If you run a breadth-first search (BFS) from an arbitrary node and then run another BFS starting from the farthest node discovered in the first BFS, then the distance computed in the second BFS is the tree diameter. In mathematical terms, if we denote by \( d(u,v) \) the distance between nodes \( u \) and \( v \), the diameter is given by:

[ \text{Diameter} = \max_{u,v \in V} d(u,v) ]

Read the input from stdin and write your answer to stdout.

inputFormat

The input is given on stdin and has the following format:

T
N
u1 v1
... (N-1 lines)
N
u1 v1
... (N-1 lines)
...

where:

• T is the number of test cases.
• For each test case, the first line contains an integer N (the number of nodes in the tree).
• The following N-1 lines each contain two integers u and v, indicating an undirected edge between nodes u and v.

outputFormat

For each test case, output a single integer on a new line — the diameter of the tree.

## sample

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

2
3

</p>