Tree Diameter

Given a tree with N nodes and its edges, compute the diameter of the tree. The diameter of a tree is defined as the number of edges on the longest path between any two nodes.

You are given multiple test cases. For each test case, the input begins with an integer N — the number of nodes in the tree. Then N - 1 lines follow, each containing two integers A and B representing an edge between nodes A and B. If N is 1, no edges are provided. Your task is to determine the diameter of each tree.

Note: Nodes are numbered from 1 to N.

inputFormat

Input is read from 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. This is followed by N - 1 lines, each containing two space-separated integers A and B, denoting an edge connecting node A and node B. For a test case where N = 1, there will be no edge lines.

outputFormat

For each test case, output a single line to standard output (stdout) containing one integer — the diameter of the tree.## sample

1
5
1 2
2 3
3 4
4 5

4