题目背景

出题人怎么还没鸟加这首歌啊。

于 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$。