CF1534D.Lost Tree

This is an interactive problem.

Little Dormi was faced with an awkward problem at the carnival: he has to guess the edges of an unweighted tree of $n$ nodes! The nodes of the tree are numbered from $1$ to $n$.

The game master only allows him to ask one type of question:

• Little Dormi picks a node $r$ ($1 \le r \le n$), and the game master will reply with an array $d_1, d_2, \ldots, d_n$, where $d_i$ is the length of the shortest path from node $r$ to $i$, for all $1 \le i \le n$.

Additionally, to make the game unfair challenge Little Dormi the game master will allow at most $\lceil\frac{n}{2}\rceil$ questions, where $\lceil x \rceil$ denotes the smallest integer greater than or equal to $x$.

Faced with the stomach-churning possibility of not being able to guess the tree, Little Dormi needs your help to devise a winning strategy!

Note that the game master creates the tree before the game starts, and does not change it during the game.

这是一个交互式问题。

小 Dormi 在嘉年华上遇到了一个棘手的问题：他必须猜出一棵包含 $n$ 个节点的无权树的所有边！这棵树的节点编号为 $1$ 到 $n$。

游戏主持人只允许他提出一种类型的问题：

• 小 Dormi 选择一个节点 $r$（$1 \le r \le n$），主持人将回复一个数组 $d_1, d_2, \ldots, d_n$，其中 $d_i$ 表示从节点 $r$ 到节点 $i$ 的最短路径长度（对所有 $1 \le i \le n$）。

此外，为了让游戏更具挑战性（且显得不太公平），主持人最多只允许提出 $\lceil\frac{n}{2}\rceil$ 个问题，其中 $\lceil x \rceil$ 表示不小于 $x$ 的最小整数。

面对可能无法猜出这棵树的令人反胃的窘境，小 Dormi 需要你的帮助来设计一个必胜策略！

注意：主持人在游戏开始前就已构造好这棵树，并在整个游戏过程中保持不变。

The first line of input contains the integer $n$ ($2 \le n \le 2\,000$), the number of nodes in the tree.

You will then begin interaction.

输入的第一行包含整数 $n$（$2 \le n \le 2\,000$），表示树中节点的数量。

随后你将开始交互。

When your program has found the tree, first output a line consisting of a single "!" followed by $n-1$ lines each with two space separated integers $a$ and $b$, denoting an edge connecting nodes $a$ and $b$ ($1 \le a, b \le n$). Once you are done, terminate your program normally immediately after flushing the output stream.

You may output the edges in any order and an edge $(a,b)$ is considered the same as an edge $(b,a)$. Answering is not considered as a query.

当你的程序找到该树后，首先输出一行，仅包含一个“!”；然后输出 $n-1$ 行，每行包含两个以空格分隔的整数 $a$ 和 $b$，表示连接节点 $a$ 和 $b$ 的一条边（$1 \le a, b \le n$）。完成输出后，请立即正常终止程序，并在终止前刷新输出流。

你可以以任意顺序输出各条边；边 $(a,b)$ 与边 $(b,a)$ 被视为同一条边。提交答案本身不被视为一次查询。

Here is the tree from the first example.

Notice that the edges can be output in any order.

Additionally, here are the answers for querying every single node in example $1$:

• $1$: $[0,1,2,2]$
• $2$: $[1,0,1,1]$
• $3$: $[2,1,0,2]$
• $4$: $[2,1,2,0]$

Below is the tree from the second example interaction.

Lastly, here are the answers for querying every single node in example $2$:

• $1$: $[0,4,1,3,2]$
• $2$: $[4,0,3,1,2]$
• $3$: $[1,3,0,2,1]$
• $4$: $[3,1,2,0,1]$
• $5$: $[2,2,1,1,0]$

以下是第一个示例中的树。

注意：边的输出顺序可以是任意的。

此外，以下是在示例 $1$ 中对每个节点分别进行查询所得到的答案：

• $1$: $[0,1,2,2]$
• $2$: $[1,0,1,1]$
• $3$: $[2,1,0,2]$
• $4$: $[2,1,2,0]$

以下是第二个示例交互中的树。

最后，以下是在示例 $2$ 中对每个节点分别进行查询所得到的答案：

• $1$: $[0,4,1,3,2]$
• $2$: $[4,0,3,1,2]$
• $3$: $[1,3,0,2,1]$
• $4$: $[3,1,2,0,1]$
• $5$: $[2,2,1,1,0]$