Hidden Permutations
Contest: Hello 2022
Difficulty rating: 1700
Tags: dfs and similar, interactive, math

This is an interactive problem.

The jury has a permutation $$$p$$$ of length $$$n$$$ and wants you to guess it. For this, the jury created another permutation $$$q$$$ of length $$$n$$$. Initially, $$$q$$$ is an identity permutation ($$$q_i = i$$$ for all $$$i$$$).

You can ask queries to get $$$q_i$$$ for any $$$i$$$ you want. After each query, the jury will change $$$q$$$ in the following way:

- At first, the jury will create a new permutation $$$q'$$$ of length $$$n$$$ such that $$$q'_i = q_{p_i}$$$ for all $$$i$$$.
- Then the jury will replace permutation $$$q$$$ with pemutation $$$q'$$$.

You can make no more than $$$2n$$$ queries in order to quess $$$p$$$.

Input format:
The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

Interaction format:
Interaction in each test case starts after reading the single integer $$$n$$$ ($$$1 \leq n \leq 10^4$$$) — the length of permutations $$$p$$$ and $$$q$$$.

To get the value of $$$q_i$$$, output the query in the format $$$?$$$ $$$i$$$ ($$$1 \leq i \leq n$$$). After that you will receive the value of $$$q_i$$$.

You can make at most $$$2n$$$ queries. After the incorrect query you will receive $$$0$$$ and you should exit immediately to get Wrong answer verdict.

When you will be ready to determine $$$p$$$, output $$$p$$$ in format $$$!$$$ $$$p_1$$$ $$$p_2$$$ $$$\ldots$$$ $$$p_n$$$. After this you should go to the next test case or exit if it was the last test case. Printing the permutation is not counted as one of $$$2n$$$ queries.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get 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.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^4$$$. The interactor is not adaptive in this problem.

Hacks:

To hack, use the following format:

The first line contains the single integer $$$t$$$ — the number of test cases.

The first line of each test case contains the single integer $$$n$$$ — the length of the permutations $$$p$$$ and $$$q$$$. The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ — the hidden permutation for this test case.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case the hidden permutation $$$p = [4, 2, 1, 3]$$$.

Before the first query $$$q = [1, 2, 3, 4]$$$ so answer for the query will be $$$q_3 = 3$$$.

Before the second query $$$q = [4, 2, 1, 3]$$$ so answer for the query will be $$$q_2 = 2$$$.

Before the third query $$$q = [3, 2, 4, 1]$$$ so answer for the query will be $$$q_4 = 1$$$.

In the second test case the hidden permutation $$$p = [1, 3, 4, 2]$$$.

Empty strings are given only for better readability. There will be no empty lines in the testing system.

Example input:
2
4

3

2

1

4

2

4

4

Example output:
? 3

? 2

? 4

! 4 2 1 3

? 2

? 3

? 2

! 1 3 4 2

Editorial:
At first, let's solve this problem when $$$p$$$ is a cycle of length $$$n$$$. It can be done by asking for $$$q_1$$$ for $$$n$$$ times. After this, we will receive $$$1$$$, $$$p_1$$$, $$$p_{p_1}$$$, $$$p_{p_{p_1}}, \ldots$$$ in this order. Since $$$p$$$ is a cycle, each $$$x$$$ will appear once in this sequence. The next element after $$$x$$$ will be $$$p_x$$$.
When $$$p$$$ is not a cycle we can determine the cycle containing the first element of permutation by asking such queries. Actually, we can stop asking queries after receiving $$$1$$$, thus determining this cycle in $$$len+1$$$ queries, where $$$len$$$ is the length of this cycle. We can determine other cycles in the same way.
We will ask $$$n$$$ queries to determine all elements and one more query for determining each cycle end, that is not more than $$$2n$$$ queries.