P7595 "EZEC-8" Guess the Tree

This is an interactive problem.

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.

See "Interaction".

See "Interaction".

**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