← 返回题目列表

Codeforces · 1979/F

F. 科斯特亚尼奇定理

中文机器翻译题面 查看原题

这是一个交互问题。

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$$$ 个顶点组成。