問題文

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

N 頂点の完全無向グラフ G があります。完全無向グラフとは、任意の異なる 2 頂点間に無向辺が 1 つあるようなグラフです。
各辺は赤か青かで塗られていますが、その色は明かされていません。

あなたは次のような質問を 2N 回 まで行うことができます。

• 頂点 i と頂点 j \ (1 \leq i , j \leq N, \ i \neq j) を繋ぐ辺 (i,j) の色を聞く。

グラフ G の全域木であって、全ての辺が同じ色で塗られているものを 1 つ出力してください。
問題の制約下で、そのようなものが必ず存在することが証明できます。

ただし、回答は質問回数に含めません。

制約

• 3 \leq N \leq 5 \times 10^4
• N は整数

入出力

この問題はインタラクティブな問題です。
まず、N が標準入力に与えられます。

N

その後、あなたは質問を行うことが出来ます。
質問は標準出力に以下の形式で出力してください(末尾に改行を入れること)。
1 \leq i , j \leq N,\ i \neq j でなければならない点に注意してください。

? i j

質問が正当な場合、その質問への答え c が標準入力から与えられます。

辺 (i,j) の色が赤ならば R, 青ならば B が与えられます。

c

質問の形式が間違っている・質問を規定の回数より多く行なったなどの理由から質問が不正と判定された場合、質問への答えの代わりに F が与えられます。

F

この時、提出は不正解と判定され、ジャッジプログラムが終了します。

出力すべき全域木 T が分かったら、 i 番目の辺が頂点 u_i と 頂点 v_i を結んでいるとして、回答を標準出力に以下の形式で出力してください(最後に改行を入れること)。

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

以下を全て満たすときに限り正解となります。

• 1 \leq u_i, v_i \leq N , \ u_i \neq v_i
• N-1 本の辺とそれらの両端の頂点からなるグラフは G の全域木である。
• N-1 本の辺は全て同じ色で塗られている。

回答を受け取った場合、答えの正誤に関わらずジャッジプログラムが終了します。

注意点

• 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
• 対話の途中で不正な出力を行った、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。
• 答えを出力したら(またはF を受け取ったら)直ちにプログラムを正常終了してください。そうしなかった場合、ジャッジ結果は不定です。
• 特に、余計な改行も不正なフォーマットの出力とみなされるので注意してください。
• 高速な方法で入出力を行うことを推奨します。
• この問題のジャッジはアダプティブです。つまり、制約および以前の出力に矛盾しない範囲でグラフの辺の色が変わる場合があります。

入出力例

以下は N=3 であり、辺 (1,2), (2,3) が赤色、辺 (1,3) が青色のグラフの場合の対話例です。