题目背景

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

题目描述

这是一道交互题。本题中，交互库是非自适应的。

作为一名研究秘密树木的学者，你遇到了一棵由 $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

A

B

? 1 2 3

? 1 4 5

!
1 3
2 3
4 3
4 5

提示

样例解释

在示例交互中，我们研究了一棵有 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$ | 无额外限制 |