「EZEC-14」终点

~~出题人怎么还没鸟加这首歌啊。~~ 于 2023.8.5 拿下。

**这是一道交互题。** dXqwq 有一棵 $n$ 个点的无根树，结点从 $1$ 到 $n$ 编号。您需要通过若干次询问得到这棵树的结构。 您可以选择两个整数 $1\leq u,v\leq n$，并输出 `? u v` 进行询问。 对于每次询问，如果 $u,v$ 的路径中点在一个结点上，交互库返回该点的编号，否则返回 ``0``。 请通过不超过 $147154$ 次询问，得到这棵树的结构。 保证树的形态是提前确定的，即**交互库不自适应。** ### 交互方式 输入测试点所在子任务编号 $id$ 和树的大小 $n$ 以开始交互。 交互过程中，您可以进行题目描述中的询问。 对于每次询问，如果你提供的 $u,v$ 不合法或者超出询问次数上限，交互库会返回 ``-1``，否则交互库将会返回一个非负整数，含义见「题目描述」。 当你读取到 ``-1`` 后应立刻退出程序，在此之后交互库的行为未定义。 在您确定答案后，请先输出 `!`，然后接下来 $n-1$ 行依次输出两个整数 ``u[i] v[i]`` 代表树的每条边，最后退出程序。你可以以任意顺序输出这些边。 在您输出一行后，请清空缓冲区： - 在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。 - 在 Pascal 中，使用 `flush(output)`。 - 在 Python 中，使用 `stdout.flush()`。 - 其它语言请自行查阅文档。

见「交互方式」。

见「交互方式」。

1 5

1

2

3

4

0

 
? 1 1

? 1 3

? 2 4

? 3 5

? 4 5

!
1 2
2 3
3 4
4 5

5 5

1

0

0

2

2

 
? 1 1

? 1 3

? 2 4

? 3 5

? 4 5

!
1 3
2 3
2 4
2 5

**本题采用捆绑测试。** - Subtask 1（10 pts）：$n \leq 10$，树满足性质 A。 - Subtask 2（10 pts）：保证存在一个点度数为 $n-1$。 - Subtask 3（10 pts）：保证所有点度数 $\leq 2$。 - Subtask 4（10 pts）：$n \leq 500$，树满足性质 A。 - Subtask 5（20 pts）：$n \leq 500$。 - Subtask 6（20 pts）：树满足性质 A。 - Subtask 7（20 pts）：无特殊限制。 性质 A：对于 $i=2,3,\cdots,n$ 存在整数 $1\leq j<i$ 满足有一条边连接 $i,j$。 对于 $100\%$ 的数据，$2 \leq n \leq 10^4$。