11551155 SUSTech Online Judge
Problem 1155 --The largest distance [Medium]

1155: The largest distance [Medium]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 544  Solved: 179
[Submit][Status][Web Board]

Description

Write a program to print the longest distance between two nodes of the given tree.

Input

The first line will be an integer T (1≤T≤10), which is the number of test cases.  

For each test data:

The first line contains two integers N (1≤N≤10^5) — the number of the nodes.

Each of the next N - 1 lines contain two integers a and b, which means there is an edge between node a and b.

Output

For each case, please print the longest distance between any two nodes of the given tree.

 

Sample Input

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

Sample Output

6

HINT

Source

[Submit][Status]