CF1979F.Kostyanych's Theorem

这是一个交互题。

Kostyanych 选择了一个有 $n$ 个顶点的完全无向图 $^{\dagger}$，然后从中恰好删除了 $(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$，收到该返回值后，你的程序应立即终止以获得 Wrong answer 判定。否则，可能会收到其他判定。

每次输出查询后，别忘了输出换行并刷新输出缓冲区，否则会收到 Idleness limit exceeded 判定。具体方法如下：

• C++：fflush(stdout) 或 cout.flush()
• Java：System.out.flush()
• Pascal：flush(output)
• Python：stdout.flush()
• 其它语言请查阅相关文档。

交互器是非自适应的。图在交互过程中不会发生变化。

Hack 格式

Hack 时请使用如下格式：

第一行包含一个整数 $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$。

在第一个测试用例中，原图如下所示：

考虑如下查询：

• 图中没有度数至少为 $3$ 的顶点，因此返回 "0 0"。
• 有四个顶点度数至少为 $2$，且它们的度数都恰好为 $2$：$1$、$2$、$3$、$4$。返回顶点 $1$（编号最小），以及与 $1$ 不相连的顶点 $4$（唯一一个）。然后移除顶点 $1$。
• 剩下三个顶点度数至少为 $1$，其中 $2$ 和 $3$ 的度数最小（为 $1$，$4$ 的度数为 $2$）。返回顶点 $2$（编号最小），以及与 $2$ 不相连的顶点 $3$（唯一一个）。然后移除顶点 $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$ 个顶点和一条边组成。

由 ChatGPT 4.1 翻译