Find the Tree Centroid

This is an interactive problem that requires you to determine the centroid of a given tree. The tree is guaranteed to have an odd number of nodes, and you are required to output the unique centroid. The centroid of a tree is defined as a node such that if it is removed, all resulting connected components have at most \(\lfloor \frac{N}{2} \rfloor\) nodes.

You are allowed to make queries using the function

[ ask(x, y, z) ]

In each query, you supply three vertices \(x, y, z\). If there is no simple path that contains all three vertices, the query returns 0. Otherwise, if the three vertices lie on some simple path, the query returns the vertex that is in the middle of these three vertices on that path. In other words, if we denote \(dis(a,b)\) as the number of edges in the shortest path between vertices \(a\) and \(b\), then:

• If \(dis(x,y)+dis(x,z)=dis(y,z)\), the query returns \(x\).
• If \(dis(y,x)+dis(y,z)=dis(x,z)\), the query returns \(y\).
• If \(dis(z,x)+dis(z,y)=dis(x,y)\), the query returns \(z\).
• Otherwise, the query returns 0.

Note: Although the problem is interactive and only supports C++ submissions in its original setting, for the purpose of this problem, you are to implement a function that computes the centroid from the provided tree structure. In the actual submission, you are required to implement the function:

int centroid(int id, int N, int M);

The parameters are as follows:

• id: the current subtask id.
• N: the number of nodes in the tree.
• M: the remaining number of queries allowed for the current test point (in the first call it is the total query limit for that test point, and it decreases with each call).

You can call the function ask(x,y,z) to interact with the judge. However, for this problem you only need to compute the centroid based on a given tree structure as input.

Input/Output Format for this non‐interactive simulation:

• The first line contains an integer \(T\) representing the number of test cases.
• For each test case, the first line contains two integers \(N\) and \(M\) (where \(M\) is provided but not used in your computation).
• The next \(N-1\) lines each contain two integers \(u\) and \(v\) indicating that there is an edge between nodes \(u\) and \(v\).

Output: For each test case, output the centroid of the tree on a new line.

inputFormat

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

• The first line contains two integers N and M (\(M\) is given for compatibility with the interactive version but is not used in the solution).
• Each of the next N-1 lines contains two integers u and v representing an edge in the tree.

It is guaranteed that \(N\) is odd.

outputFormat

For each test case, output the centroid of the tree on a separate line.

sample

1
3 10
1 2
1 3

1

</p>