406144: GYM102279 B Beggin' For A Node

This is an interactive problem

Low_ has a beautiful tree, which he keeps very carefully. A tree is a tree, but mathematically, it could be modeled as an indirect connected graph with no cycles. Suppose low_'s tree has $$$n$$$ nodes and $$$n-1$$$ edges.

S_e_o is low_'s friend, and he has been attracted to the Codeforces golden secret for a long time. He does not want to hurt his friend by taking it illegally, especially from his beloved tree, so S_e_o comes up with a devious plan. He hides the golden secret in a node of low_'s favorite tree and challenges him to find that node by interacting with an A.I bot which was created by another hacker named b21. There are two types of question that low_ could beg for:

"$$$?\;1\;u$$$": The bot will return number of edges on the simple path from node u to the hidden node.

"$$$?\;2\;u$$$": The bot will return the second node on the simple path from node u to the hidden node. If this type of query is asked for the hidden node by luck, the bot will return $$$0$$$.

Low_ does not want his friend to read his own secret to become master at Codeforces, so he has to be quick. Please help him, and remember to be quick by only asking no more than 36 queries.

The first line contains an integer $$$n$$$ ($$$1\le n\le 200000$$$).

The next $$$n-1$$$ lines, each contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$) denotes that there's an edge connects $$$u$$$ and $$$v$$$ in the tree.

You can make queries of type "? T u" to the robot. $$$T$$$ is either $$$1$$$ or $$$2$$$, and $$$1 \le u \le n$$$. The description for query is stated in the problem legend.

After the query read its result as an integer. If you read $$$-1$$$, that means your query is in the wrong format, or you have exceeded $$$36$$$ queries. Exit the program immediately to get the verdict "Wrong answer". If you don't, you might get an arbitrary verdicts.

When you find out the array, print "!" followed by a space and an integer denotes your answer. This is not counted as a query, but you only have one guess. If you failed to get the answer right, your verdict will be "Wrong answer".

After printing any query do not forget to output end of line and flush the output. Otherwise you will get Idleness limit exceeded. To do this, use:

fflush(stdout) or cout.flush() in C++;

System.out.flush() in Java;

flush(output) in Pascal;

stdout.flush() in Python.

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

1

3

0

? 2 2

? 1 6

? 1 3

! 3