Festival Ground Location

Given a collection of n villages connected by n-1 bidirectional roads that form a tree, your task is to determine the optimal village to build a festival ground. The optimal village is defined as the one that maximizes the minimum distance to any other village. In essence, you need to choose the center of the tree.

This can be achieved by finding the longest path (the diameter of the tree) and then selecting the middle node on that path. Mathematically, if the diameter has length d, then the center is the node at distance $\left\lfloor\frac{d}{2}\right\rfloor$ from one end of the diameter.

inputFormat

The first line of input contains an integer T, denoting the number of test cases. For each test case:

• The first line contains an integer n (the number of villages).
• The next n - 1 lines each contain two space-separated integers u and v, representing a bidirectional road between villages u and v.

You may assume that the given roads form a tree.

outputFormat

For each test case, output the optimal village number (the center of the tree) on a new line.

1
1

1