10621062 SUSTech Online Judge
Problem 1062 --Two tourists problem

1062: Two tourists problem

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 734  Solved: 153
[Submit][Status][Web Board]


There are N cities in a country. The roads between the cities form a binary Tree with the cities. Two tourists A and B start at the same city (which can be any city). They want to arrive at two cities such that the distance of the cities is as large as possible. Please find the distance.

Note that all the length of the road is always 1. And when you calculate the distance, one road can be calculated at most once.


First line is an integer T, which is the number of test cases. (1 <= T <= 50)

For each test case, there will be an integer in a single line N (1 <= N <= 10000). N is the number of nodes. The nodes are numbered from 1 to N.

Then there will be N – 1 lines with two integer x, y for each line. (1 <= x, y <= N)

x y means x is the farther of y. What’s more, we guarantee the input file is a tree. And the children are labeled from left to right by the order they appear.


For each test case, print the largest distance problem required.

Sample Input

1 4
1 3
4 2
2 7
3 5
3 6
6 8

Sample Output



Hard problem.