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](https://www.luogu.com.cn/user/1340759)