Capital Relocation Problem

A country consists of n cities connected by n - 1 bidirectional roads forming a tree. The king wishes to relocate the capital to a new city such that the maximum distance from that city to any other city is minimized. In other words, the new capital must be one of the central cities of the tree. When there are two possible central cities, choose the one with the smaller number.

You are given multiple test cases. For each test case, you are given the number of cities and the list of roads connecting them. Your task is to determine the optimal city for the capital according to the rule described above.

inputFormat

The input is read from standard input. The first line contains an integer T, the number of test cases. Each test case is described as follows:

• The first line contains a single integer n representing the number of cities.
• The following n-1 lines each contain two space-separated integers u and v indicating a bidirectional road between city u and city v.

It is guaranteed that the cities form a tree.

outputFormat

For each test case, output a single line containing an integer: the number of the chosen capital city. If there are two central cities, output the smaller one.## sample

3
4
1 2
2 3
3 4
5
1 2
1 3
3 4
3 5
6
1 2
1 3
2 4
2 5
3 6

2
1
1