311389: CF1979F. Kostyanych's Theorem

F. Kostyanych's Theoremtime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is an interactive problem.

Kostyanych has chosen a complete undirected graph$^{\dagger}$ with $n$ vertices, and then removed exactly $(n - 2)$ edges from it. You can ask queries of the following type:

• "? $d$" — Kostyanych tells you the number of vertex $v$ with a degree at least $d$. Among all possible such vertices, he selects the vertex with the minimum degree, and if there are several such vertices, he selects the one with the minimum number. He also tells you the number of another vertex in the graph, with which $v$ is not connected by an edge (if none is found, then $0$ is reported). Among all possible such vertices, he selects the one with the minimum number. Then he removes the vertex $v$ and all edges coming out of it. If the required vertex $v$ is not found, then "$0\ 0$" is reported.

Find a Hamiltonian path$^{\ddagger}$ in the original graph in at most $n$ queries. It can be proven that under these constraints, a Hamiltonian path always exists.

$^{\dagger}$A complete undirected graph is a graph in which there is exactly one undirected edge between any pair of distinct vertices. Thus, a complete undirected graph with $n$ vertices contains $\frac{n(n-1)}{2}$ edges.

$^{\ddagger}$A Hamiltonian path in a graph is a path that passes through each vertex exactly once.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains a single integer $n$ ($2 \le n \le 10^5$) — the number of vertices in the graph.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Interaction

Interaction for each test case begins with reading the integer $n$.

Then you can make no more than $n$ queries.

To make a query, output a line in the format "? $d$" (without quotes) ($0 \le d \le n - 1$). After each query, read two integers — the answer to your query.

When you are ready to report the answer, output a line in the format "! $v_1\ v_2 \ldots v_n$" (without quotes) — the vertices in the order of their occurrence in the Hamiltonian path. Outputting the answer does not count as one of the $n$ queries. After solving one test case, the program should immediately move on to the next one. After solving all test cases, the program should be terminated immediately.

If your program makes more than $n$ queries for one test case or makes an incorrect query, then the response to the query will be $-1$, and after receiving such a response, your program should immediately terminate to receive the verdict Wrong answer. Otherwise, it may receive any other verdict.

After outputting a query, do not forget to output an end of line and flush the output buffer. Otherwise, you will receive the verdict Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

The interactor is non-adaptive. The graph does not change during the interaction.

Hacks

To hack, use the following format:

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The only line of each test case contains a single integer $n$ ($2 \le n \le 10^5$) — the number of vertices in the graph.

Each of the following $(n - 2)$ lines should contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$) — ends of the edge that was removed from the graph. Each edge must not occur more than once.

The sum of $n$ over all test cases should not exceed $10^5$.

ExampleInput

3
4

0 0

1 4

2 3

4

1 0

4 2

2

1 0

Output

? 3

? 2

? 1

! 4 3 1 2

? 3

? 0

! 4 1 2 3

? 0

! 2 1

Note

In the first test case, the original graph looks as follows:

Consider the queries:

• There are no vertices with a degree of at least $3$ in the graph, so "$0\ 0$" is reported.
• There are four vertices with a degree of at least $2$, and all of them have a degree of exactly $2$: $1$, $2$, $3$, $4$. Vertex $1$ is reported, because it has the minimum number, and vertex $4$ is reported, because it is the only one not connected to vertex $1$. After this, vertex $1$ is removed from the graph.
• There are three vertices with a degree of at least $1$, among them vertices $2$ and $3$ have a minimum degree of $1$ (vertex $4$ has a degree of $2$). Vertex $2$ is reported, because it has the minimum number, and vertex $3$ is reported, because it is the only one not connected to vertex $2$. After this, vertex $2$ is removed from the graph.

The path $4 - 3 - 1 - 2$ is a Hamiltonian path.

In the second test case, the original graph looks as follows:

Consider the queries:

• Vertex $1$ has a degree of at least $3$, but it is connected to all vertices, so "$1\ 0$" is reported. After this, vertex $1$ is removed from the graph.
• The remaining vertices $2$, $3$, and $4$ have a degree of at least $0$, but among them vertex $4$ has the minimum degree of $0$ (vertices $2$ and $3$ have a degree of $1$). Vertex $4$ is not connected to both vertices $2$ and $3$, so vertex $2$ is reported (as it has the minimum number). After this, vertex $4$ is removed from the graph.

The path $4 - 1 - 2 - 3$ is a Hamiltonian path.

In the third test case, the graph consists of $2$ vertices connected by an edge.

### 科斯蒂亚涅奇定理

**题目大意**：这是一个交互式问题。科斯蒂亚涅奇选择了一个具有n个顶点的完全无向图，然后从中精确地移除了(n-2)条边。你可以提出以下类型的查询：

- 问号后跟数字d：科斯蒂亚涅奇会告诉你顶点v的度数至少为d。在所有可能的这样的顶点中，他会选择度数最小的顶点，如果有几个这样的顶点，他会选择编号最小的顶点。他还会告诉你图中另一个与v没有连接边的顶点（如果没有找到，则报告0）。在所有可能这样的顶点中，他会选择编号最小的顶点。然后他会移除顶点v及其所有出边。如果找不到所需的顶点v，则报告"0 0"。

你的任务是找到原始图中的哈密尔顿路径，在不超过n次查询的情况下。可以证明，在这些约束条件下，总是存在哈密尔顿路径。

**输入输出数据格式**：

- **输入**：每个测试用例包含多个测试案例。第一行包含一个整数t（1≤t≤1000）——测试案例的数量。接下来是测试案例的描述。
每个测试案例只有一行，包含一个整数n（2≤n≤10^5）——图中顶点的数量。
保证所有测试案例的n之和不超过10^5。

- **输出**：对于每个测试案例，交互开始于读取整数n。
然后你可以进行不超过n次查询。
要进行查询，以格式"?\ d"（不带引号）输出一行（0≤d≤n-1）。每次查询后，读取两个整数——对你查询的答案。
当你准备好报告答案时，以格式"! v1 v2 ... vn"（不带引号）输出一行——按照哈密尔顿路径中顶点的出现顺序输出顶点。输出答案不计入n次查询之一。解决一个测试案例后，程序应立即进行下一个。解决所有测试案例后，程序应立即终止。

- 如果你的程序对一个测试案例进行超过n次查询或进行错误的查询，则查询的响应将是-1，在收到这样的响应后，你的程序应立即终止以获得错误答案的判决。否则，它可能会收到任何其他判决。

- 输出查询后，别忘了输出换行符并刷新输出缓冲区。否则，你将收到超时限制的判决。根据你使用的编程语言，使用适当的方法来刷新输出缓冲区。

- **交互器**是非自适应的。图在交互期间**不会改变**。

- **破解**：使用以下格式进行破解：
- 第一行包含一个整数t（1≤t≤1000）——测试案例的数量。
- 每个测试案例只有一行，包含一个整数n（2≤n≤10^5）——图中顶点的数量。
- 接下来的(n-2)行应包含两个整数u和v（1≤u, v≤n，u≠v）——从图中移除的边的端点。每条边不得出现多次。
- 所有测试案例的n之和不应超过10^5。

- **示例**和**注意**部分提供了如何与程序交互以及如何找到哈密尔顿路径的详细说明和示例。### 科斯蒂亚涅奇定理 **题目大意**：这是一个交互式问题。科斯蒂亚涅奇选择了一个具有n个顶点的完全无向图，然后从中精确地移除了(n-2)条边。你可以提出以下类型的查询： - 问号后跟数字d：科斯蒂亚涅奇会告诉你顶点v的度数至少为d。在所有可能的这样的顶点中，他会选择度数最小的顶点，如果有几个这样的顶点，他会选择编号最小的顶点。他还会告诉你图中另一个与v没有连接边的顶点（如果没有找到，则报告0）。在所有可能这样的顶点中，他会选择编号最小的顶点。然后他会移除顶点v及其所有出边。如果找不到所需的顶点v，则报告"0 0"。 你的任务是找到原始图中的哈密尔顿路径，在不超过n次查询的情况下。可以证明，在这些约束条件下，总是存在哈密尔顿路径。 **输入输出数据格式**： - **输入**：每个测试用例包含多个测试案例。第一行包含一个整数t（1≤t≤1000）——测试案例的数量。接下来是测试案例的描述。 每个测试案例只有一行，包含一个整数n（2≤n≤10^5）——图中顶点的数量。 保证所有测试案例的n之和不超过10^5。 - **输出**：对于每个测试案例，交互开始于读取整数n。 然后你可以进行不超过n次查询。 要进行查询，以格式"?\ d"（不带引号）输出一行（0≤d≤n-1）。每次查询后，读取两个整数——对你查询的答案。 当你准备好报告答案时，以格式"! v1 v2 ... vn"（不带引号）输出一行——按照哈密尔顿路径中顶点的出现顺序输出顶点。输出答案不计入n次查询之一。解决一个测试案例后，程序应立即进行下一个。解决所有测试案例后，程序应立即终止。 - 如果你的程序对一个测试案例进行超过n次查询或进行错误的查询，则查询的响应将是-1，在收到这样的响应后，你的程序应立即终止以获得错误答案的判决。否则，它可能会收到任何其他判决。 - 输出查询后，别忘了输出换行符并刷新输出缓冲区。否则，你将收到超时限制的判决。根据你使用的编程语言，使用适当的方法来刷新输出缓冲区。 - **交互器**是非自适应的。图在交互期间**不会改变**。 - **破解**：使用以下格式进行破解： - 第一行包含一个整数t（1≤t≤1000）——测试案例的数量。 - 每个测试案例只有一行，包含一个整数n（2≤n≤10^5）——图中顶点的数量。 - 接下来的(n-2)行应包含两个整数u和v（1≤u, v≤n，u≠v）——从图中移除的边的端点。每条边不得出现多次。 - 所有测试案例的n之和不应超过10^5。 - **示例**和**注意**部分提供了如何与程序交互以及如何找到哈密尔顿路径的详细说明和示例。