Interactive Tree Hidden Point

This is an interactive problem.

You are given a tree with \(n\) nodes. The structure of the tree is provided as input. There is a hidden node \(s\) on the tree. In each query, you can propose a node \(u\). The interactor will then choose one of two operations:

• If it chooses Operation 1, it moves \(s\) one step toward \(u\) (if \(s = u\), nothing happens) and outputs 1.
• If it chooses Operation 2, it outputs 2 \(d\) where \(d\) is the current distance from \(u\) to \(s\).

Your task is to determine the current position of \(s\) within at most \(m\) queries for each test case. Each test case consists of \(T\) groups of data. Note that the interactor is non‐adaptive: the hidden \(s\) is chosen before any queries are made, and the interactor follows the fixed procedure regardless of your queries.

Interaction Protocol:

• First, you are given a positive integer \(T\) representing the number of test cases.
• For each test case, the first line contains two positive integers \(n\) and \(m\), representing the number of nodes in the tree and the limit on query count.
• The next \(n-1\) lines each contain two integers \(u\) and \(v\), indicating an edge between nodes \(u\) and \(v\).
• You then proceed with interactive queries. Each query should be in the format ? u (with \(1 \le u \le n\)). If you exceed the query limit \(m\) in a test case, the interactor outputs -1 and your program must terminate immediately.
• If the query count is within the limit, the interactor will respond either with 1 (indicating Operation 1 was performed) or with 2 d (indicating Operation 2 was performed and providing the current distance \(d\) from \(u\) to \(s\)).
• When you are ready to answer, output ! u where \(u\) is your guess for the current position of \(s\). If your guess is correct, the interactor outputs 1 and moves to the next test case; otherwise it outputs 0 and terminates your program.

Remember to flush the output after every output (e.g., using fflush(stdout) in C/C++ or equivalent in other languages).

Note: In each test file, the total number of queries over all test cases does not exceed \(\sum m\). This guarantees that the interactor runs within time and space limits.

inputFormat

The input begins with a positive integer \(T\), the number of test case groups.

For each test case:

• A line with two integers \(n\) and \(m\): the number of nodes in the tree and the query limit.
• \(n - 1\) subsequent lines, each containing two integers \(u\) and \(v\), indicating an edge between nodes \(u\) and \(v\).

outputFormat

This is an interactive problem.

During interaction, output your queries in the format ? u and flush the output. Once you have determined the current position of \(s\) in the tree, output your answer as ! u (where \(u\) is the node number) and flush the output. The interactor will respond accordingly.

sample

1
3 5
1 2
1 3

! 1

</p>