C. Leafy Distance
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Sampo is hiding inside a tunnel system. The tunnel can be modeled as a tree$$$^{\text{∗}}$$$ with $$$n$$$ nodes and $$$n-1$$$ edges. There is an exit situated at every node with exactly one neighbor.

Sampo wants to decide in which node to hide in. Obviously, he should hide in a node that is the furthest distance away from any exit. Please help Sampo determine which node is the best one to hide in. If there are multiple nodes that are equally as far from an exit, output the node with the least index.

$$$^{\text{∗}}$$$A tree is a connected graph without cycles.

Input

The first line contains an integer $$$t$$$ – the number of test cases ($$$1 \leq t \leq 10^4$$$).

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$) – the number of nodes in the tree.

The following $$$n-1$$$ lines each contain two integers $$$p$$$ and $$$q$$$ ($$$1 \leq p, q \leq n, p\neq q$$$) – signifying that there is an edge from $$$p$$$ to $$$q$$$ in the tree. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Scoring

Partial credits will be given to programs who pass tests with smaller constraints outlined below.

GroupPointsConstraints
140The sum of $$$n$$$ does not exceed $$$1500$$$ over all test cases
260No further constraints
Output

For each test case, output the index of the node furthest away from any exit. If there are multiple nodes that are equally far, output the node with the least index.

Example
Input
4
3
1 3
2 3
4
1 2
2 3
4 2
4
1 2
2 3
3 4
13
1 2
2 3
3 4
4 5
4 6
2 7
7 8
2 9
6 10
5 11
11 12
10 13
Output
3
2
2
4
Note
This is the tree in the first test case. Node $$$3$$$ is distance $$$1$$$ away from exits, while nodes $$$1$$$ and $$$2$$$ are distance $$$0$$$ away from exits.