Genokraken
Contest: Codeforces Round 983 (Div. 2)
Difficulty rating: 1800
Tags: constructive algorithms, data structures, graphs, greedy, implementation, interactive, trees, two pointers

This is an interactive problem.

Upon clearing the Waterside Area, Gretel has found a monster named Genokraken, and she's keeping it contained for her scientific studies.

The monster's nerve system can be structured as a tree$$$^{\dagger}$$$ of $$$n$$$ nodes (really, everything should stop resembling trees all the time$$$\ldots$$$), numbered from $$$0$$$ to $$$n-1$$$, with node $$$0$$$ as the root.

Gretel's objective is to learn the exact structure of the monster's nerve system — more specifically, she wants to know the values $$$p_1, p_2, \ldots, p_{n-1}$$$ of the tree, where $$$p_i$$$ ($$$0 \le p_i < i$$$) is the direct parent node of node $$$i$$$ ($$$1 \le i \le n - 1$$$).

She doesn't know exactly how the nodes are placed, but she knows a few convenient facts:

- If we remove root node $$$0$$$ and all adjacent edges, this tree will turn into a forest consisting of only paths$$$^{\ddagger}$$$. Each node that was initially adjacent to the node $$$0$$$ will be the end of some path.
- The nodes are indexed in a way that if $$$1 \le x \le y \le n - 1$$$, then $$$p_x \le p_y$$$.
- Node $$$1$$$ has exactly two adjacent nodes (including the node $$$0$$$).

The tree in this picture does not satisfy the condition, because if we remove node $$$0$$$, then node $$$2$$$ (which was initially adjacent to the node $$$0$$$) will not be the end of the path $$$4-2-5$$$.The tree in this picture does not satisfy the condition, because $$$p_3 \le p_4$$$ must hold.The tree in this picture does not satisfy the condition, because node $$$1$$$ has only one adjacent node.

Gretel can make queries to the containment cell:

- "? a b" ($$$1 \le a, b < n$$$, $$$a \ne b$$$) — the cell will check if the simple path between nodes $$$a$$$ and $$$b$$$ contains the node $$$0$$$.

However, to avoid unexpected consequences by overstimulating the creature, Gretel wants to query at most $$$2n - 6$$$ times. Though Gretel is gifted, she can't do everything all at once, so can you give her a helping hand?

$$$^{\dagger}$$$A tree is a connected graph where every pair of distinct nodes has exactly one simple path connecting them.

$$$^{\ddagger}$$$A path is a tree whose vertices can be listed in the order $$$v_1, v_2, \ldots, v_k$$$ such that the edges are $$$(v_i, v_{i+1})$$$ ($$$1 \le i < k$$$).

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

The first line of each test case contains a single integer $$$n$$$ ($$$4 \le n \le 10^4$$$) — the number of nodes in Genokraken's nerve system.

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

Interaction format:
For each test case, interaction starts by reading the integer $$$n$$$.

Then you can make queries of the following type:

- "? a b" (without quotes) ($$$1 \le a, b < n$$$, $$$a \ne b$$$).

After the query, read an integer $$$r$$$ — the answer to your query. You are allowed to use at most $$$2n - 6$$$ queries of this type.

- If the simple path between nodes $$$a$$$ and $$$b$$$ does not contain node $$$0$$$, you will get $$$r = 0$$$.
- If the simple path between nodes $$$a$$$ and $$$b$$$ contains node $$$0$$$, you will get $$$r = 1$$$.
- In case you make more than $$$2n-6$$$ queries or make an invalid query, you will get $$$r = -1$$$. You will need to terminate after this to get the "Wrong answer" verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

When you find out the structure, output a line in the format "! $$$p_1 \space p_2 \ldots p_{n-1}$$$" (without quotes), where $$$p_i$$$ ($$$0 \le p_i < i$$$) denotes the index of the direct parent of node $$$i$$$. This query is not counted towards the $$$2n - 6$$$ queries limit.

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.

After printing any query do not forget to output an end of line and flush the output buffer. 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.

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

Hacks

For hack, use the following format:

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

The first line of each test case contains a single integer $$$n$$$ ($$$4 \le n \le 10^4$$$) — the number of nodes in Genokraken's nerve system.

The second line of each test case contains $$$n-1$$$ integers $$$p_1, p_2, \ldots, p_{n-1}$$$ ($$$0 \le p_1 \le p_2 \le \ldots \le p_{n-1} \le n - 2$$$, $$$0 \le p_i < i$$$) — the direct parents of node $$$1$$$, $$$2$$$, ..., $$$n-1$$$ in the system, respectively.

In each test case, the values $$$p_1, p_2, \ldots, p_{n-1}$$$ must ensure the following in the tree:

- If we remove root node $$$0$$$ and all adjacent edges, this tree will turn into a forest consisting of only paths. Each node that was initially adjacent to the node $$$0$$$ will be the end of some path.
- Node $$$1$$$ has exactly two adjacent nodes (including the node $$$0$$$).

The sum of $$$n$$$ over all test cases must not exceed $$$10^4$$$.

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

Note:
In the first test case, Genokraken's nerve system forms the following tree:

- The answer to "? 2 3" is $$$1$$$. This means that the simple path between nodes $$$2$$$ and $$$3$$$ contains node $$$0$$$.

In the second test case, Genokraken's nerve system forms the following tree:

- The answer to "? 2 3" is $$$1$$$. This means that the simple path between nodes $$$2$$$ and $$$3$$$ contains node $$$0$$$.
- The answer to "? 2 4" is $$$0$$$. This means that the simple path between nodes $$$2$$$ and $$$4$$$ doesn't contain node $$$0$$$.

In the third test case, Genokraken's nerve system forms the following tree:

Example input:
3
4

1

5

1

0

9

Example output:
? 2 3

! 0 0 1

? 2 3

? 2 4

! 0 0 1 2

! 0 0 0 1 3 5 6 7

Editorial:
For simplicity, we'll use the term "tentacle" to call each path tree in the forest made by cutting off node $$$0$$$. We also notice that in each tentacle, two nodes will never have the same distance from root node $$$0$$$.
The condition of $$$p_x \le p_y$$$ iff $$$x \le y$$$ leads to a crucial observation of the system: it is indexed in accordance to a BFS order of the tree. Hence, we now have two goals:
1. Determine $$$m$$$ — the number of tentacles.
2. From node $$$m+1$$$ to $$$n-1$$$, assign every node to their respective tentacles. Due to the BFS order, at the moment of assignment, the previous tip of the tentacle is the parent of the current node, and the current node becomes the new tip of the tentacle.
For the first objective, we see that node $$$1$$$ is guaranteed to be connected with nodes $$$0$$$ and $$$m + 1$$$. Furthermore, $$$m + 1$$$ is the first non-zero node where the path between it and $$$1$$$ does not cross $$$0$$$. Therefore, you can keep querying $$$(1, j)$$$ for increasing $$$j$$$ until you find a $$$0$$$ to get $$$m$$$.
For the second objective, we need to find the tentacle that each node $$$i$$$ ($$$m + 2 \le i \le n - 1$$$) belongs to; in other words, find the node $$$1 \le i \le m$$$ so that query $$$(i, j)$$$ yields a $$$0$$$. Denote $$$t(j)$$$ as the tentacle associated with node $$$j$$$, then note that:
• If $$$j-1$$$ and $$$j$$$ share the same distance from $$$0$$$, then obviously $$$t(j-1) < t(j)$$$, i.e., $$$t(j)$$$ will be a tentacle at the forward direction from $$$t(j-1)$$$ in the tentacle list.
• If $$$j-1$$$ and $$$j$$$ don't share the same distance from $$$0$$$, then $$$t(j)$$$ can be any tentacle in the list.
So we can approach this objective like this: denote $$$\text{next}(t(j-1))$$$ as the next tentacle in the list after $$$t(j-1)$$$ (or $$$1$$$ if $$$t(j-1)$$$ was at the end of the list), starting from $$$i = t(j-1)$$$, we'll keep re-assigning $$$i = \text{next}(i)$$$ until query $$$(i, j)$$$ yields a $$$0$$$.
From hindsight, it looks like we'll need $$$\mathcal{O}(n^2)$$$ query count order to finish this part, but there is another crucial observation: due to the nodes being indexed in BFS order, if any tentacle yields a $$$1$$$ during probing, that tentacle will never be extended again — proof for this is pretty intuitive but a bit lengthy to express in words, so we'll leave it as an exercise for the reader — thus if you reach an $$$i$$$ that has already been deactivated before, you ignore it and call $$$\text{next}$$$ again, which wouldn't count towards the queries as it is your internal processing.
Let's count the number of queries we used. Let $$$m \le n - 2$$$ be the number of tentacles, then
• If $$$m = n-2$$$, the second objective wouldn't be needed, so we end up with $$$n - 2 \le 2n - 6$$$ queries in total (as $$$n \le 4$$$).
• If $$$m \le n - 3$$$, note that each time we process a query, either a node is appended to a tentacle, or a tentacle is removed. Since at most $$$m - 1$$$ tentacles can be removed and there are $$$n - m - 2$$$ nodes to be processed, the second phase uses at most $$$n - 3$$$ queries, so in total we use $$$n + m - 3 \le 2n - 6$$$ queries.
To process the list of tentacles, there are a few options:
• Naively mark the tentacles as active/inactive to know when to stop by for queries and when to skip. Time complexity will be $$$\mathcal{O}(n^2)$$$, and though it can still pass (in fact one such solution from the author passed nicely), it is not recommended.
• Maintain the list of tentacles in a set, if a node is known to be inactive, remove it. Time complexity will be $$$\mathcal{O}(n \log n)$$$.
• Maintain the list of tentacles in a similar manner as above, but using a doubly linked list this time. Time complexity will be $$$\mathcal{O}(n)$$$.