Contents

• # For Solution

There is a tree consisting of NN nodes. A certain node XX is marked as special, but you don’t know XX – your task is to find it. To achieve this, you can ask queries to obtain information about XX.

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

Find the Special Node solution codechef? Y

where 1YN1≤Y≤N, and you will be provided with a random node on the path from node YY to node XX, excluding YY. If Y=XY=X you will receive 1−1 instead.

You can ask at most 1212 queries. Find the special node XX.

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

### Interaction Find the Special Node solution codechef

• Begin the interaction by reading a single integer TT denoting the number of test cases. The test cases follow.
• For each test case, first read a single integer NN denoting the number of nodes in the tree.
• N1N−1 lines follow. The ithith of these lines contains two space-separated integers uiui and vivi, denoting an edge between the nodes uiui and vivi.
• After this, you can start making queries.
• To ask a query, output ? Y (1YN1≤Y≤N). The judge will return some node (other than YY) which lies on the path between node YY and node XX, or 1−1 if Y=XY=X.
• To output the answer, output ! X, where XX 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

• 1T101≤T≤10
• 3N10003≤N≤1000
• 1ui,viN1≤ui,vi≤N
• It is guaranteed that the given nodes and edges construct a tree.
• 1XN1≤X≤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 Find the Special Node solution codechef

• Test case 11: X=1X=1.

• The query ? 1 gives 1−1.
• A query returns 1−1 only if Y=XY=X, hence we can answer X=1X=1.
• Test case 22: X=3X=3.

• The query ? 1 gives node 22 which is in the path from node 11 to node 33 excluding node 11. That is the path between node 22 to node 33.
• The query ? 2 gives node 33 which is in the path from node 22 to node 44 excluding node 22. That is the path between node 33 to node 33.
• The query ? 3 gives 1−1 as Y=XY=X in this case, hence we can answer node 33.

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