{"problem":{"name":"「EZEC-14」终点","description":{"content":"**这是一道交互题。** dXqwq 有一棵 $n$ 个点的无根树，结点从 $1$ 到 $n$ 编号。您需要通过若干次询问得到这棵树的结构。 您可以选择两个整数 $1\\leq u,v\\leq n$，并输出 `? u v` 进行询问。 对于每次询问，如果 $u,v$ 的路径中点在一个结点上，交互库返回该点的编号，否则返回 ``0``。 请通过不超过 $147154$ 次询问，得到这棵树的结构","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9462"},"statements":[{"statement_type":"Markdown","content":"**这是一道交互题。**\n\ndXqwq 有一棵 $n$ 个点的无根树，结点从 $1$ 到 $n$ 编号。您需要通过若干次询问得到这棵树的结构。\n\n您可以选择两个整数 $1\\leq u,v\\leq n$，并输出 `? u v` 进行询问。\n\n对于每次询问，如果 $u,v$ 的路径中点在一个结点上，交互库返回该点的编号，否则返回 ``0``。\n\n请通过不超过 $147154$ 次询问，得到这棵树的结构。\n\n保证树的形态是提前确定的，即**交互库不自适应。**\n\n### 交互方式\n\n输入测试点所在子任务编号 $id$ 和树的大小 $n$ 以开始交互。\n\n交互过程中，您可以进行题目描述中的询问。\n\n对于每次询问，如果你提供的 $u,v$ 不合法或者超出询问次数上限，交互库会返回 ``-1``，否则交互库将会返回一个非负整数，含义见「题目描述」。\n\n当你读取到 ``-1`` 后应立刻退出程序，在此之后交互库的行为未定义。\n\n在您确定答案后，请先输出 `!`，然后接下来 $n-1$ 行依次输出两个整数 ``u[i] v[i]`` 代表树的每条边，最后退出程序。你可以以任意顺序输出这些边。\n\n在您输出一行后，请清空缓冲区：\n\n- 在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。\n- 在 Pascal 中，使用 `flush(output)`。\n- 在 Python 中，使用 `stdout.flush()`。\n- 其它语言请自行查阅文档。\n\n## Input\n\n见「交互方式」。\n\n## Output\n\n见「交互方式」。\n\n[samples]\n\n## Background\n\n~~出题人怎么还没鸟加这首歌啊。~~\n\n于 2023.8.5 拿下。\n\n## Note\n\n**本题采用捆绑测试。**\n\n- Subtask 1（10 pts）：$n \\leq 10$，树满足性质 A。\n- Subtask 2（10 pts）：保证存在一个点度数为 $n-1$。\n- Subtask 3（10 pts）：保证所有点度数 $\\leq 2$。\n- Subtask 4（10 pts）：$n \\leq 500$，树满足性质 A。\n- Subtask 5（20 pts）：$n \\leq 500$。 \n- Subtask 6（20 pts）：树满足性质 A。\n- Subtask 7（20 pts）：无特殊限制。\n\n性质 A：对于 $i=2,3,\\cdots,n$ 存在整数 $1\\leq j