問題文

この問題はインタラクティブな問題です。

$N$ 頂点 $N-1$ 辺の木が与えられます。頂点には $1,2,\dots,N$ と、辺には $1,2,\dots,N-1$ と番号がつけられていて、辺 $i$ は頂点 $u_i$ と頂点 $v_i$ を相互に結びます。はるく君は、このうちちょうど $1$ つの頂点にお宝を隠しました。

あなたは、$15$ 回まで以下のクエリをはるく君に送ることができます。

• 長さ $N-1$ の整数列 $x=(x_1,x_2,\dots,x_{N-1})$ を指定し、はるく君に送る。ただし、$1\leq i\leq N-1$ について、$x_i=u_i$ または $x_i=v_i$ でなくてはならない。$x$ の値が相異なる必要はない。
• はるく君は、頂点 $x_1,x_2,\dots,x_{N-1}$ の中にお宝のある頂点が含まれているかをあなたに教える。

お宝のある頂点を特定してください。

制約

• $1\leq N\leq 10000$
• $1\leq u_i,v_i\leq N$ $(1\leq i\leq N-1)$
• 与えられるグラフは木である
• 入力はすべて整数

入出力

この問題はインタラクティブな問題です。

最初に、$N,(u_1,v_1),(u_2,v_2),\dots,(u_{N-1},v_{N-1})$ が標準入力から与えられます。

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

次に、あなたははるく君に $15$ 回までクエリを送ることができます。整数列 $x=(x_1,x_2,\dots,x_{N-1})$ を指定してクエリを送るとき、以下のように出力してください。末尾に改行を入れることを忘れないでください。

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

クエリを送ると、はるく君からの返答が以下の形式で与えられます。

$S$

ここで、$S$ は Yes または No または Invalid で、

• $S$ が Yes のとき、指定された頂点の中にお宝のある頂点が存在することを表します。
• $S$ が No のとき、指定された頂点の中にお宝のある頂点が存在しないことを表します。
• $S$ が Invalid のとき、$x$ が制約を満たしていないか、クエリを送った回数が $15$ 回を超えたことを表します。
  • このとき、プログラムはすでに不正解とみなされています。ただちにプログラムを終了してください。

お宝が頂点 $t$ にあると特定できたら、以下のように $t$ を出力してください。これはクエリの回数には計上されません。

! $t$

この出力のあと、ただちにプログラムを終了してください。

上記のいずれの形式にも当てはまらない出力をした場合は、Invalid が標準入力から与えられます。

Invalid

このときも、プログラムはすでに不正解とみなされています。ただちにプログラムを終了してください。

注意点

• 出力を行うたびに、末尾に改行を入れて標準出力をflushしてください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
• 解答を出力したとき、または Invalid を標準入力から受け取ったとき、ただちにプログラムを終了してください。そうしなかった場合の判定結果は不定です。
• 余計な改行は不正なフォーマットの出力とみなされることに注意してください。
• この問題のジャッジシステムは適応的です。 つまり、ジャッジは過去のクエリと整合性がとれる限り、お宝のある頂点を変更することがあります。

入出力例

$N=5,u=(1,1,1,2),v=(2,3,4,5)$ で、ジャッジははるく君が頂点 $1$ にお宝を隠したと想定しているときの対話の一例を示します。

これは対話の一例であることに注意してください。また、この問題のジャッジシステムは適応的であることから、このやりとりによって正解と判定されるとは限りません。