题目描述

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

有一棵 $N$ 个节点的树。这棵树中，每个节点度数至多为 $3$。

你可以提问至多 $K=2.5\times 10^5$ 次。每次给定三个两两不同的节点 $a,b,c$，交互库会回答：

• $\text{0}$，如果 $\operatorname{dist}(a,b)=\operatorname{dist}(a,c)$;
• $\text{1}$，如果 $\operatorname{dist}(a,b)\lt\operatorname{dist}(a,c)$;
• $\text{2}$，如果 $\operatorname{dist}(a,b)\gt\operatorname{dist}(a,c)$。

定义 $\operatorname{dist}(u,v)$ 表示 $u,v$ 最短路上边的数量。

试通过询问还原这棵树。

虽然你可以提问 $K=2.5\times 10^5$ 次，但是想要获得更高的分数，需要更少的询问次数。见「计分方式」。

实现细节

首先读入正整数 $N$。读入后发起询问：

• $\texttt{?}$ $a$ $b$ $c$：发起一次询问。
  • 你需要保证 $1 \leq a, b, c \leq N$ 且 $a \neq b$，$b \neq c$，$c \neq a$。
  • 最多可以询问 $2.5\times 10^5$ 次。
  • 从标准输入流读入一个整数表示答案，具体见「题目描述」。
• $\texttt{!}$：报告答案。
  • 输出 $\texttt{!}$ 后，接下来再输出 $(N-1)$ 行，每行两个正整数，描述一条树边。
  • 你可以以任意顺序输出这 $(N-1)$ 条边。
  • 报告答案后，你的程序必须终止运行。

每次提问后，都需要换行并刷新缓冲区。

交互库是非自适应的。也就是说，树的形态在交互开始前已经固定。

输入格式

见「实现细节」。

输出格式

见「实现细节」。

4

1

2

0

? 1 2 3

? 1 4 3

? 2 1 3

!
1 2
2 3
3 4

提示

样例解释

样例中，树边有 $\{(1,2),(2,3),(3,4)\}$。

数据范围

• $N\lt 512$；
• 每个节点度数至多为 $3$。

子任务

• $\text{Subtask 0 (0 pts)}$：样例。
• $\text{Subtask 1 (10 pts)}$：每个节点度数至多为 $2$。
• $\text{Subtask 2 (20 pts)}$：树是满二叉树。
  • 换句话说，树是完全二叉树，且存在正整数 $k$ 使得 $N=2^k-1$。
• $\text{Subtask 3 (70 pts)}$：无额外限制。

计分方式

答案错误，询问次数超限，或者出现了任何未能成功运行结束的情况，得 $0$ 分。

假设你在某个分值为 $B$ 的子任务中至多用了 $K$ 次查询，则子任务得分为

$$\min\left(1, \left(\frac{14000}{K}\right)^{0.7}\right) \cdot B $$

交互库是非自适应的。也就是说，树的形态在交互开始前已经固定。