Codeforces Round 951 (Div. 2) |
---|
Finished |
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:
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.
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 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:
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$$$.
3 4 0 0 1 4 2 3 4 1 0 4 2 2 1 0
? 3 ? 2 ? 1 ! 4 3 1 2 ? 3 ? 0 ! 4 1 2 3 ? 0 ! 2 1
In the first test case, the original graph looks as follows:
Consider the queries:
The path $$$4 - 3 - 1 - 2$$$ is a Hamiltonian path.
In the second test case, the original graph looks as follows:
Consider the queries:
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.
Name |
---|