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

KSA惑星には $N$ 個の島があります。島には $1$ から $N$ までの番号が付けられており、島 $i$ には $w_i$ の資源があります。異なる島で資源の量が同じになることはありません。島の間には $N-1$ 本の双方向の水中通路があり、どの2つの島も水中通路のみを通って到達できることが保証されています。言い換えれば、島と水中通路が形成する構造は木です。

KSA惑星の水中通路が他の惑星からは見えないことに気づいたKSA惑星の王であるアリスは、島同士を結ぶ $N-1$ 本の双方向の地上橋を新たに追加建設することを計画しています。これらの橋のみを使用して、どの2つの島の間も移動可能でなければなりません。つまり、橋の構造も木を形成する必要があります。

アリスが橋の建設を終えると、オートマタ惑星の王であるボブが情報を解明しようと試みます。このとき、島の番号は任意に再割り当てされ、それ以降、ボブが観測または使用するすべての島番号は、この再割り当てされた番号付けシステムに従います。

ボブは、アリスが建設した地上橋のみを見て、すべての $1 \le i, j \le N$ について $x(i, j)$ を決定しなければなりません。ここで、

です。ここで、開始島番号 $i$、目的地島番号 $j$、および資源量が最大である島の番号はすべて、再割り当てされた番号付けシステムに基づいています。島番号 $i$ から島番号 $j$ への経路には、島番号 $i$ と島番号 $j$ の両方が含まれます。

すべての $x(i, j)$ の値を決定する前に、ボブは追加情報を得るために最大 $100$ 回まで以下の質問をすることができます。

• `?` $i$ $j$ : $x(i, j)$ は何か？

惑星間通信は非常に高価であるため、質問回数が少ないほどスコアが高くなります。

あなたのプログラムは、各判定データに対して2回実行されます。1回目の実行ではアリスの役割を、2回目の実行ではボブの役割を果たす必要があります。

最初の行には、実行ステップを示す整数 $S$ が含まれます。$S=1$ はアリスとしてプレイすることを、$S=2$ はボブとしてプレイすることを意味します。

アリスの役割

入力: 入力は1つ以上のテストケースで構成されます。2行目にはテストケースの数 $T$ が含まれます。各テストケースは以下のように与えられます。

最初の行には島の数 $N$ が含まれます。

2行目には $N$ 個のスペース区切りの整数 $w_1, w_2, \cdots, w_N$ が含まれます。

続く $N-1$ 行の各行には、水中通路の端点である2つのスペース区切りの整数 $u, v$ が含まれます。

出力: 建設する地上橋の端点である2つのスペース区切りの整数 $u, v$ を含む $N-1$ 行を出力してください。橋を出力する順序は問わず、各橋における2つの端点の順序も問いません。

ボブの役割

インタラクション: 入力は1つ以上のテストケースで構成されます。2行目にはテストケースの数 $T$ が含まれます。各テストケースは以下のように与えられます。

最初の行には島の数 $N$ が含まれます。

続く $N-1$ 行の各行には、アリスが建設した地上橋の端点である2つのスペース区切りの整数 $u, v$ が含まれます。$u$ と $v$ は再割り当てされた番号付けシステムを使用しており、ボブが受け取る橋の順序はアリスが出力した順序と異なる場合があることに注意してください。

追加情報が必要な場合、以下のクエリを出力すると、次の行に $x(i, j)$ の値が与えられます。このクエリはテストケースごとに最大 $100$ 回まで使用できます。

• `?` $i$ $j$ ($1 \le i, j \le N$)

回答を提出するには、`!` を出力し、続いて次の $N$ 行に回答を出力してください。$N$ 行のうち $i$ 行目には、$x(i, 1), x(i, 2), \cdots, x(i, N)$ をスペース区切りで出力する必要があります。このクエリは質問回数にはカウントされず、出力直後に該当するテストケースのインタラクションは終了します。

最後のテストケースではないテストケースでインタラクションが終了した場合、直ちに次のテストケースに進まなければなりません。最後のテストケースのインタラクションが終了した場合、プログラムは直ちに終了しなければなりません。

ただし、1つのテストケースで $100$ 回を超える質問が行われた場合、クエリへの応答として `-1` が与えられ、許可された質問回数を超過したことを示します。この場合、プログラムは直ちに終了しなければならず、結果は Wrong Answer と判定されます。

制約

• $S \in \{1, 2 \}$
• $1 \le T \le 100$
• $2 \le N \le 100$
• $1 \le u < v \le N$
• $1 \le w_i \le 10^9$
• $i \ne j$ ならば $w_i \neq w_j$

スコア

各判定データについて、$Q$ をすべてのテストケースの中で質問された最大回数とします。その判定データのスコアは以下のように決定されます。

提出のスコアは、すべての判定データセットにおける最小スコアとなります。ただし、問題で提供された制限内で適切なインタラクションを通じて解を出力しない場合、予期しない結果が発生する可能性があります。

入出力例

入力 1

1
2
4
3 5 9 4
1 2
2 3
2 4



2
10 1
1 2

出力 1

1 4
2 3
3 4



1 2

入力 2

2
2
4
1 3
1 4
2 3

4

1





2
1 2

2

出力 2

? 2 3

? 1 2

!
1 1 1 1
1 2 4 4
1 4 3 4
1 4 4 4


? 1 2

!
1 2
2 2

注記

例1では、$S = 1$ であるため、プログラムはアリスの役割を果たす必要があります。

例2では、$S = 2$ であるため、プログラムはボブの役割を果たす必要があります。

1番目のテストケースでは、1回目の実行時の頂点 $1, 2, 3, 4$ がそれぞれ頂点 $2, 4, 1, 3$ に再割り当てされました。

2番目のテストケースでは、1回目の実行時の頂点 $1, 2$ がそれぞれ頂点 $2, 1$ に再割り当てされました。

何かを出力した直後に必ずフラッシュを行ってください。フラッシュには以下を使用できます。

• C --- `fflush(stdout)`
• C++ --- `std::cout.flush()`
• Python --- `sys.stdout.flush()`
• Java --- `System.out.flush()`
• その他の言語についてはドキュメントを参照してください。

また、例の入出力における空行は分かりやすくするためのものであり、実際のインタラクションでは発生しません。