P9462 "EZEC-14" Destination

~~Why hasn’t the problem setter added this song yet.~~ Got it on 2023.8.5.

**This is an interactive problem.** dXqwq has an unrooted tree with $n$ nodes, numbered from $1$ to $n$. You need to determine the structure of this tree through several queries. You may choose two integers $1 \leq u, v \leq n$, and output `? u v` to make a query. For each query, if the midpoint of the path between $u$ and $v$ is a node, the interactor returns the index of that node; otherwise it returns `0`. You must determine the structure of the tree using no more than $147154$ queries. It is guaranteed that the tree is fixed in advance, i.e., **the interactor is not adaptive.** ### Interaction Protocol At the start, read the subtask id $id$ of the testpoint and the size of the tree $n$. During the interaction, you may make the queries described above. For each query, if the $u, v$ you provide are invalid or you exceed the maximum number of queries, the interactor will return `-1`. Otherwise, the interactor will return a non-negative integer with the meaning described in the **Description** section. After reading `-1`, you should exit the program immediately. After that, the interactor’s behavior is undefined. After you have determined the answer, first output `!`, then output $n-1$ lines, each containing two integers `u[i] v[i]` representing each edge of the tree, and then exit the program. You may output the edges in any order. After outputting each line, flush the output 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. ## Constraints See **Interaction Protocol**.

See **Interaction Protocol**.

See **Interaction Protocol**.

**This problem uses bundled tests.** - Subtask 1 (10 pts): $n \leq 10$, the tree satisfies Property A. - Subtask 2 (10 pts): It is guaranteed that there exists a node with degree $n-1$. - Subtask 3 (10 pts): It is guaranteed that all nodes have degree $\leq 2$. - Subtask 4 (10 pts): $n \leq 500$, the tree satisfies Property A. - Subtask 5 (20 pts): $n \leq 500$. - Subtask 6 (20 pts): the tree satisfies Property A. - Subtask 7 (20 pts): no special constraints. Property A: For $i = 2, 3, \cdots, n$, there exists an integer $1 \leq j < i$ such that there is an edge connecting $i$ and $j$. For $100\%$ of the testdata, $2 \leq n \leq 10^4$.  Translated by ChatGPT 5