Find the Special Node ( DSA INTERVIEW PREPARATION PROBLEMS AND SOLUTIONS ) ~ Multiplex Coder

This is an interactive task

There is a tree consisting of $N$ nodes. A certain node $X$ is marked as special, but you don't know $X$ - your task is to find it. To achieve this, you can ask queries to obtain information about $X$ .

To be specific, you can ask queries in the form:

? Y

where $1 \leq Y \leq N$ , and you will be provided with a random node on the path from node $Y$ to node $X$ , excluding $Y$ . If $Y = X$ you will receive $- 1$ instead.

You can ask at most $12$ queries. Find the special node $X$ .

Note: The judge is not adaptive, i.e, node $X$ is chosen at the start before any interaction happens and does not change based on the queries you ask.

Interaction

Begin the interaction by reading a single integer $T$ denoting the number of test cases. The test cases follow.
For each test case, first read a single integer $N$ denoting the number of nodes in the tree.
$N - 1$ lines follow. The $i^{t h}$ of these lines contains two space-separated integers $u_{i}$ and $v_{i}$ , denoting an edge between the nodes $u_{i}$ and $v_{i}$ .
After this, you can start making queries.
To ask a query, output ? Y ( $1 \leq Y \leq N$ ). The judge will return some node (other than $Y$ ) which lies on the path between node $Y$ and node $X$ , or $- 1$ if $Y = X$ .
To output the answer, output ! X, where $X$ is the special node that is hidden. This is not considered a query.
If at any time you make an invalid query or exceed the query limit, the interaction is terminated and you will receive a Wrong Answer verdict.
Don't forget to flush the output after printing each line!

Constraints

$1 \leq T \leq 10$
$3 \leq N \leq 1000$
$1 \leq u_{i}, v_{i} \leq N$
It is guaranteed that the given nodes and edges construct a tree.
$1 \leq X \leq N$

Sample Interaction

Grader                You
2
4
1 2
1 3
1 4
                      ? 1
-1
                      ! 1
4
1 2
2 3
3 4 
                      ? 1 
2          
                      ? 2
3
                      ? 3
-1
                      ! 3

Explanation

Test case $1$ : $X = 1$ .
- The query ? 1 gives $- 1$ .
- A query returns $- 1$ only if $Y = X$ , hence we can answer $X = 1$ .
Test case $2$ : $X = 3$ .
- The query ? 1 gives node $2$ which is in the path from node $1$ to node $3$ excluding node $1$ . That is the path between node $2$ to node $3$ .
- The query ? 2 gives node $3$ which is in the path from node $2$ to node $4$ excluding node $2$ . That is the path between node $3$ to node $3$ .
- The query ? 3 gives $- 1$ as $Y = X$ in this case, hence we can answer node $3$ .

NOTE: The above queries are just to demonstrate the interaction. They may or may not be sufficient to deduce the final answer.