E. Cyber Hide-and-Seek
time limit per test
3.9 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
The real is the rational, and the rational is the real.
— G.W.F.Hegel, Grundliniender Philosophiedes Rechts

This is an interactive problem.

One day, you wake up to find Miku in front of you. Instead of singing, she wants to play a game with you!

This game is played on a tree with $$$n$$$ nodes, which is rooted at node $$$1$$$. A tree is a connected graph without cycles.

Miku has hidden a fufu at node $$$x$$$. You need to ask Miku the following two types of queries to find the location of it:

  • $$$1~u$$$ $$$(1 \le u \le n)$$$. Miku will tell you the distance between node $$$u$$$ and node $$$x$$$. Here, the distance between two nodes denotes the number of edges in the shortest path between them.
  • $$$2~v$$$ $$$(1 \le v \le n)$$$. Miku will tell you the second node on the shortest path from node $$$v$$$ to node $$$x$$$. However, when executing this query, you need to ensure that $$$v$$$ is an ancestor of $$$x$$$$$$^{\dagger}$$$, or you will immediately receive a Wrong Answer verdict due to Miku's unhappiness.

$$$^{\dagger}$$$ Node $$$a$$$ is an ancestor of node $$$b$$$ if and only if $$$a\neq b$$$, and the shortest path from node $$$1$$$ to node $$$b$$$ passes through $$$a$$$. Note that in this problem, node $$$a$$$ is not an ancestor of $$$a$$$ itself.

Can you find $$$x$$$ within $$$39$$$ queries? If you do, Miku will give you a fufu as a reward!

Input

The first line contains a single integer $$$n$$$ $$$(2 \le n \le 3.9 \times 10^5)$$$, denoting the number of nodes in the tree.

The $$$i$$$-th of the next $$$n-1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$), denoting the $$$i$$$-th edge on the tree.

It is guaranteed that the input edges form a tree.

Interaction

To make a query, you can output one of the following two formats:

  • $$$1~u$$$ ($$$1 \le u \le n$$$), or
  • $$$2~v$$$ ($$$1 \le v \le n$$$).

After making a query, you should read the corresponding response, which represents the distance from $$$u$$$ to $$$x$$$ or the second node on the path from $$$v$$$ to $$$x$$$, depending on your query.

If the response you read is $$$-1$$$, it means that you may have exceeded the number of allowed queries, made an invalid query, or violated the restriction for the second type of query. In this case, you should immediately exit the program and receive a Wrong Answer verdict; otherwise, you may receive a random verdict other than Accepted.

After printing a query, do not forget to output end of line and flush the output. Otherwise, you will get Runtime Error. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • stdout.flush() in Python.

To print the answer, please output "! x" (Without quotes). Note that giving this answer is not counted towards the limit of $$$39$$$ queries.

Example
Input
5
1 2
1 3
3 4
3 5

3

4
Output





1 2

2 3

! 4
Note

In the example, the hidden fufu is at node $$$x = 4$$$.

The tree in the example

You can make the following queries:

  1. Ask the distance between node $$$2$$$ and $$$x$$$, and get the reply $$$3$$$. It can be inferred that $$$x = 4$$$ or $$$5$$$;
  2. Ask the second node from node $$$3$$$ to $$$x$$$, and get the reply $$$4$$$. Note that node $$$3$$$ is the parent node of node $$$x$$$, so the second node is node $$$x$$$. Therefore, $$$x = 4$$$;

Output the answer $$$4$$$, and you can get the reward.

Note that this is not the only way to get the answer.