这是一个交互问题。
Kostyanych 选择了一个完整的无向图$$$^{\dagger}$$$,具有 $$$n$$$ 个顶点,然后从中删除了 $$$(n - 2)$$$ 条边。您可以提出以下类型的查询:
- "? $$$d$$$" — Kostyanych 告诉你度数至少为 $$$d$$$ 的顶点 $$$v$$$ 的数量。在所有可能的这样的顶点中,他选择度数最小的顶点,如果这样的顶点有多个,他选择数量最小的一个。他还告诉您图中另一个顶点的编号,$$$v$$$ 没有通过边连接(如果没有找到,则报告 $$$0$$$)。在所有可能的此类顶点中,他选择数量最少的一个。然后他删除顶点 $$$v$$$ 以及从该顶点出来的所有边。如果未找到所需的顶点 $$$v$$$,则报告“$$$0\ 0$$$”。
在最多$$$n$$$个查询中在原始图中找到哈密顿路径$$$^{\ddagger}$$$。可以证明,在这些约束下,哈密顿路径始终存在。
$$$^{\dagger}$$$完全无向图是指任意一对不同顶点之间恰好存在一条无向边的图。因此,具有 $$$n$$$ 个顶点的完全无向图包含 $$$\frac{n(n-1)}{2}$$$ 边。
$$$^{\ddagger}$$$图中的哈密顿路径是只经过每个顶点一次的路径。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) - 测试用例的数量。测试用例的描述如下。
每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 图中的顶点数。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
互动
每个测试用例的交互都从读取整数 $$$n$$$ 开始。
那么您最多可以进行 $$$n$$$ 查询。
要进行查询,请以“? $$$d$$$”格式输出一行(不带引号)($$$0 \le d \le n - 1$$$)。每次查询后,读取两个整数——查询的答案。
当您准备好报告答案时,请以“! $$$v_1\ v_2 \ldots v_n$$$”(不带引号)格式输出一行 — 顶点按照其在哈密顿路径中出现的顺序排列。输出答案不算作 $$$n$$$ 查询之一。解决一个测试用例后,程序应立即转到下一个测试用例。解决所有测试用例后,程序应立即终止。
如果你的程序对一个测试用例进行了超过 $$$n$$$ 查询或者进行了错误的查询,那么对查询的响应将为 $$$-1$$$,并且在收到这样的响应后,你的程序应该立即终止以接收判定错误的答案。否则,它可能会收到任何其他判决。
输出查询后,不要忘记输出行尾并刷新输出缓冲区。否则,您将收到超出空闲限制的判决。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
交互器是非自适应的。交互过程中图形不会发生变化。
黑客
要破解,请使用以下格式:
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 图中的顶点数。
以下 $$$(n - 2)$$$ 行均应包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — 从图中删除的边的末端。每条边不得出现多次。
所有测试用例的 $$$n$$$ 总和不应超过 $$$10^5$$$。
示例
输入 #1
3 4 0 0 1 4 2 3 4 1 0 4 2 2 1 0
输出 #1
? 3 ? 2 ? 1 ! 4 3 1 2 ? 3 ? 0 ! 4 1 2 3 ? 0 ! 2 1
注意
在第一个测试用例中,原始图如下所示:
考虑查询:
- 图中没有度数至少为 $$$3$$$ 的顶点,因此报告“$$$0\ 0$$$”。
- 有四个顶点的度数至少为 $$$2$$$,并且所有顶点的度数都恰好为 $$$2$$$:$$$1$$$、$$$2$$$、$$$3$$$、$$$4$$$。报告顶点 $$$1$$$,因为它具有最小数量,报告顶点 $$$4$$$,因为它是唯一一个未连接到顶点 $$$1$$$ 的顶点。此后,顶点 $$$1$$$ 将从图中删除。
- 有三个顶点的度数至少为 $$$1$$$,其中顶点 $$$2$$$ 和 $$$3$$$ 的最小度数为 $$$1$$$(顶点 $$$4$$$ 的度数为 $$$2$$$)。报告顶点 $$$2$$$,因为它具有最小数量,报告顶点 $$$3$$$,因为它是唯一一个未连接到顶点 $$$2$$$ 的顶点。此后,顶点 $$$2$$$ 将从图中删除。
路径 $$$4 - 3 - 1 - 2$$$ 是哈密顿路径。
在第二个测试用例中,原始图如下所示:
考虑查询:
- 顶点 $$$1$$$ 的度数至少为 $$$3$$$,但它连接到所有顶点,因此报告“$$$1\ 0$$$”。此后,顶点 $$$1$$$ 将从图中删除。
- 其余顶点 $$$2$$$、$$$3$$$ 和 $$$4$$$ 的度数至少为 $$$0$$$,但其中顶点 $$$4$$$ 的最小度数为 $$$0$$$(顶点 $$$2$$$ 和 $$$3$$$ 的度数为 $$$1$$$)。顶点 $$$4$$$ 未连接到顶点 $$$2$$$ 和 $$$3$$$,因此报告顶点 $$$2$$$(因为它具有最小编号)。此后,顶点 $$$4$$$ 将从图中删除。
路径 $$$4 - 1 - 2 - 3$$$ 是哈密顿路径。
在第三个测试用例中,该图由通过边连接的 $$$2$$$ 个顶点组成。