P14012 [POCamp 2023] 枫树 / Maple Tree

**为便于本地测试，我们在附件中提供了评测工具。使用说明见文件开头的注释。**

**这是一道交互题。本题中，交互库是非自适应的。** 作为一名研究秘密树木的学者，你遇到了一棵由 $N$ 个节点和 $N-1$ 条不同长度边组成的树，**所有边的长度均为正**。此外，**已知每个节点的度数不超过 $\bf 3$**。 确定这棵树的结构——也就是哪些节点彼此相连——并不容易，但你获得了一台可能有帮助的装置。该装置可以比较树上的距离。令 $d(x,y)$ 表示节点 $x$ 与 $y$ 之间路径上所有边长之和。使用装置一次时，给定三个节点 $A, B, C$（其中 $A \neq B$），你可以比较 $d(A,C)$ 与 $d(B,C)$ 的大小。 在最多使用装置 $20\, 000$ 次的前提下，你能找出树上存在哪些边吗？你不需要求出边的具体长度。 ### 实现细节 你的程序应首先读入一个整数 $N$（$3 \le N \le 1000$），表示树的节点数。 随后你可以开始使用装置进行至多 20,000 次测量。每次测量时，你应输出一行，格式为 `? A B C`（$1 \le A, B, C \le N,\ A \neq B$），然后读入一行，内容为字符 `A`（若 $d(A,C) < d(B,C)$）或 `B`（若 $d(A,C) > d(B,C)$）。保证对所有 $A \neq B$，都有 $d(A,C) \neq d(B,C)$。 最后，你应输出一行字符 `!`，接着输出 $N-1$ 行，每行给出树中的一条边。每行包含两个整数 $a, b$（$1 \le a, b \le N$），表示该边连接的两个节点。 **在每次查询后，都要刷新缓冲区**。例如：C++ 中的 `cout.flush()`。 保证每个测试点中的树在交互开始前已固定，不会根据你的测量结果自适应改变。 **为便于本地测试，我们在附件中提供了评测工具。使用说明见文件开头的注释。**

见「实现细节」。

见「实现细节」。

### 样例解释 在示例交互中，我们研究了一棵有 5 个节点的枫树。利用测量装置，确定了从节点 1 到 3 的路径长度短于从 2 到 3 的路径长度，以及从 1 到 5 的路径长度长于从 4 到 5 的路径长度。基于这些信息，猜测该树包含四条边 $(1,3)$、$(2,3)$、$(4,3)$ 和 $(4,5)$。实际上，要确定树的结构仍需进行更多次测量。 ### 子任务 **本题采用捆绑测试。** | 子任务编号 | 得分 | 限制 | |:-:|:-:|---| | $1$ | $10$ | $N \le 30$ | | $2$ | $15$ | $N \le 175$ | | $3$ | $40$ | $N \le 350$ | | $4$ | $10$ | 树是一条链 | | $5$ | $25$ | 无额外限制 |