CF2001C.Guess The Tree

这是一道交互题。

Misuki 有一棵结构未知，具有 $n$ 个节点的树，节点编号从 $ 1 $ 到 $ n $ ，并要求你写一份代码来猜测它。

你可以询问以下问题：

? a b

其中 $a,b$ 为两个节点的编号。

对于一次询问，Misuki 会告诉你哪个节点 $x$ 能最小化 $|d(a,x)-d(b,x)|$ 的值，其中 $d(x,y)$ 是节点 $x$ 和 $y$ 之间的距离。如果存在多个这样的节点，Misuki 会告诉你最小化 $d(a,x)$ 的节点。

现要求你使用不超过 $15n$ 次的询问，来确定这棵树的结构。

本题有多组测试数据。 第一行一个正整数 $t$ ，代表测试样例的个数，$1 \le t \le 200 $。

对于每组测试数据，一行一个正整数 $n$（$2 \le n \le 1000$），代表树中的节点数。

保证所有测试数据中 $n$ 的总和不超过 $1000$。

交互从读取整数 $n$ 开始，
然后你最多可以进行 $15n$ 次查询。在每个查询后，读取一个整数作为查询的答案。

要输出答案，请按如下格式输出：

！$a_1$ $b_1$ $a_2$ $b_2$ ... $a_{n-1}$ $b_{n-1}$

这意味着对于 $1 \le i \le n-1$，节点 $ a_i $ 和 $ b_i $ 之间有一条边。你可以按任意顺序输出边。

在进行 $15n$ 次查询后，若再进行查询，将读取到 $-1$ 。收到 $-1$ 后，请终止程序以接收 Wrong Answer 判定。

打印每一行后（即进行一次询问或输出一次答案后），请输出回车并刷新输出缓冲区。可刷新输出缓冲区的有：

• C++ 中的 fflush(stdout) 或 cout.flush();
• Java 中的 System.out.flush();
• Pascal 中的 flush(output);
• Python 中的 stdout.flush();
• 对于其他语言，请参阅其他语言的文档。

Translated by @ARIS2_0