這是一個互動式問題。

在 KSA 星球上有 $N$ 個島嶼。島嶼編號為 $1$ 到 $N$，島嶼 $i$ 擁有 $w_i$ 數量的資源。沒有兩個不同的島嶼擁有相同數量的資源。島嶼之間有 $N-1$ 條雙向水下通道，且保證任意兩個島嶼之間僅透過水下通道即可互相抵達。換句話說，由島嶼和水下通道組成的結構是一棵樹。

在意識到 KSA 星球上的水下通道從其他星球無法被看見後，KSA 的國王 Alice 計畫額外建造 $N-1$ 條連接島嶼對的雙向地面橋樑。僅使用這些橋樑，也必須能夠在任意兩個島嶼之間通行。也就是說，橋樑結構也必須構成一棵樹。

當 Alice 完成橋樑建設後，Automata 星球的國王 Bob 開始嘗試挖掘資訊。此時，島嶼編號會被任意重新分配，從那時起，Bob 觀察或使用的每個島嶼編號都遵循此重新分配後的編號系統。

Bob 必須僅透過觀察 Alice 建造的地面橋樑來確定所有 $1 \le i, j \le N$ 的 $x(i, j)$，其中：

這裡，起始島嶼編號 $i$、目標島嶼編號 $j$ 以及擁有最大資源量的島嶼編號，皆基於重新分配後的編號系統。從島嶼編號 $i$ 到島嶼編號 $j$ 的路徑包含島嶼編號 $i$ 和島嶼編號 $j$ 本身。

在確定所有 $x(i, j)$ 的值之前，Bob 最多可以詢問以下問題 $100$ 次以獲取額外資訊：

• `?` $i$ $j$ ：$x(i, j)$ 是多少？

由於星際通訊非常昂貴，詢問次數越少，得分越高。

您的程式在每個評測資料中會被執行兩次。在第一次執行時，它必須扮演 Alice 的角色；在第二次執行時，它必須扮演 Bob 的角色。

第一行包含一個整數 $S$，表示執行步驟。$S=1$ 表示扮演 Alice，$S=2$ 表示扮演 Bob。

Alice 的角色

輸入格式：輸入包含一個或多個測試案例。第二行包含測試案例數量 $T$。每個測試案例的格式如下：

第一行包含島嶼數量 $N$。

第二行包含 $N$ 個以空格分隔的整數 $w_1, w_2, \cdots, w_N$。

接下來的 $N-1$ 行，每行包含兩個以空格分隔的整數 $u, v$，表示水下通道的兩個端點。

輸出格式：輸出 $N-1$ 行，每行包含兩個以空格分隔的整數 $u, v$，表示要建造的地面橋樑的兩個端點。列印橋樑的順序不重要，每條橋樑中兩個端點的順序也不重要。

Bob 的角色

互動：輸入包含一個或多個測試案例。第二行包含測試案例數量 $T$。每個測試案例的格式如下：

第一行包含島嶼數量 $N$。

接下來的 $N-1$ 行，每行包含兩個以空格分隔的整數 $u, v$，表示 Alice 建造的地面橋樑的兩個端點。請注意，$u$ 和 $v$ 使用的是重新分配後的編號系統，且 Bob 接收到橋樑的順序可能與 Alice 列印的順序不同。

若需額外資訊，當列印以下查詢時，下一行將包含 $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)$，並以空格分隔。此查詢不計入詢問次數，且對應測試案例的互動在列印後立即結束。

如果某個測試案例的互動結束且不是最後一個測試案例，則必須立即進行下一個測試案例。如果最後一個測試案例的互動結束，程式必須立即終止。

然而，如果在單個測試案例中詢問超過 $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

Note

在範例 1 中，由於 $S = 1$，您的程式必須扮演 Alice 的角色。

在範例 2 中，由於 $S = 2$，您的程式必須扮演 Bob 的角色。

在第一個測試案例中，第一次執行時的頂點 $1, 2, 3, 4$ 分別被重新分配為頂點 $2, 4, 1, 3$。

在第二個測試案例中，第一次執行時的頂點 $1, 2$ 分別被重新分配為頂點 $2, 1$。

您必須在列印內容後立即刷新輸出。若要刷新，可以使用：

• C --- `fflush(stdout)`
• C++ --- `std::cout.flush()`
• Python --- `sys.stdout.flush()`
• Java --- `System.out.flush()`
• 其他語言請參閱相關文件。

此外，請注意範例輸入和輸出中的空行僅為了清晰起見，在實際互動中不會出現。