Problem Statement

This is an interactive problem.

You are given a tree with $N$ vertices and $N-1$ edges. The vertices are numbered $1,2,\dots,N$ and the edges are numbered $1,2,\dots,N-1$, and edge $i$ connects vertex $u_i$ and vertex $v_i$ bidirectionally. Haruku has hidden a treasure at exactly $1$ of these vertices.

You may send Haruku the following query up to $15$ times.

• Specify an integer sequence $x=(x_1,x_2,\dots,x_{N-1})$ of length $N-1$ and send it to Haruku. Here, for $1\leq i\leq N-1$, it must hold that $x_i=u_i$ or $x_i=v_i$. The values of $x$ do not need to be distinct.
• Haruku tells you whether the vertex with the treasure is among the vertices $x_1,x_2,\dots,x_{N-1}$.

Identify the vertex with the treasure.

Constraints

• $1\leq N\leq 10000$
• $1\leq u_i,v_i\leq N$ $(1\leq i\leq N-1)$
• The given graph is a tree.
• All input values are integers.

Input and Output

This is an interactive problem.

First, $N,(u_1,v_1),(u_2,v_2),\dots,(u_{N-1},v_{N-1})$ are given from standard input.

$N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$

Next, you may send Haruku up to $15$ queries. To send a query specifying an integer sequence $x=(x_1,x_2,\dots,x_{N-1})$, output as follows. Do not forget to add a newline at the end.

? $x_1$ $x_2$ $\dots$ $x_{N-1}$

After you send a query, Haruku's response is given in the following format.

$S$

Here, $S$ is Yes, No, or Invalid:

• If $S$ is Yes, the vertex with the treasure is among the specified vertices.
• If $S$ is No, the vertex with the treasure is not among the specified vertices.
• If $S$ is Invalid, either $x$ does not satisfy the constraints or the number of queries sent has exceeded $15$.
  • In this case, your program has already been judged as incorrect. Terminate the program immediately.

Once you have identified that the treasure is at vertex $t$, output $t$ as follows. This does not count toward the number of queries.

! $t$

After this output, terminate the program immediately.

If you produce output that does not match any of the formats above, Invalid is given from standard input.

Invalid

In this case as well, your program has already been judged as incorrect. Terminate the program immediately.

Notes

• Each time you output, add a newline at the end and flush standard output. Otherwise, the verdict may be TLE.
• When you have output your answer or received Invalid from standard input, terminate the program immediately. Otherwise, the verdict is undefined.
• Note that extra newlines are regarded as incorrectly formatted output.
• The judge system for this problem is adaptive. That is, the judge may change the vertex with the treasure as long as it remains consistent with the previous queries.

Sample Interaction

Here is an example of an interaction for $N=5,u=(1,1,1,2),v=(2,3,4,5)$, where the judge assumes that Haruku has hidden the treasure at vertex $1$.

Note that this is only one example of an interaction. Also, since the judge system for this problem is adaptive, this exchange is not necessarily judged as correct.