这是一个交互式问题。

在 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 | 25 | $60 < Q \le 100$ | | 2 | 37 | $20 < Q \le 60$ | | 3 | 50 | $4 < Q \le 20$ | | 4 | 62 | $Q = 4$ | | 5 | 75 | $Q = 3$ | | 6 | 100 | $Q \le 2$ |

你的提交得分为所有评测数据中的最低得分。但是，如果你没有在题目规定的限制内通过正确的交互打印解决方案，可能会出现意外结果。

样例

输入格式 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$，你的程序必须扮演 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()`
• 其他语言请查阅相关文档。

此外，请注意样例输入和输出中的空行仅为了清晰起见，在实际交互中不会出现。