Description

There is a rooted tree with $n$ nodes, rooted at $1$. You need to determine the structure of this tree by making several queries.

You may use two types of queries:

1. ? 1 u v Using this query, you can obtain the distance between $u$ and $v$.
2. ? 2 u Using this query, you can obtain the size of the subtree of $u$ and all nodes in the subtree of $u$.

Please determine the structure of the tree while making the interactive library output no more than $10^5$ numbers.

Interaction

The interaction starts by reading the tree size $n$.

During the interaction, you may make the two types of queries described above.

For the first type of query, the interactive library will return a non-negative integer, representing the distance between node $u$ and node $v$.

For the second type of query, the interactive library will first return a positive integer $num$, representing the size of the subtree of $u$. Then, on the same line, it will return $num$ positive integers, representing all nodes in the subtree of $u$ (the order of nodes will be shuffled).

After you have determined the answer, output one line in the form ! fa[2] fa[3] ... fa[n] and stop the interaction. Here, $fa[i]$ denotes the parent of node $i$ in this tree.

After outputting a line, flush the buffer:

• In C++, use fflush(stdout) or cout.flush().
• In Pascal, use flush(output).
• In Python, use stdout.flush().
• For other languages, please check the documentation yourself.

Input Format

See "Interaction".

Output Format

See "Interaction".

5

1

5 1 5 2 4 3

3 4 2 5

1 3

? 1 1 2

? 2 1

? 2 2

? 2 3

! 1 1 2 2

Hint

This problem uses bundled testdata.

• Subtask 1 (5 points): $n \leq 5$.
• Subtask 2 (15 points): $n \leq 100$.
• Subtask 3 (20 points): $n \leq 500$.
• Subtask 4 (15 points): the tree is a chain.
• Subtask 5 (15 points): the tree is a complete binary tree.
• Subtask 6 (30 points): no special constraints.

For $100\%$ of the data: $2 \leq n \leq 2000$, $1 \le u,v \le n$.

Note: continuing to query after making an invalid query or after the interactive library has output more than $10^5$ numbers may cause TLE.

Translated by ChatGPT 5