Background

Why hasn’t the problem setter added this song yet.

Got it on 2023.8.5.

Problem Description

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.

Input Format

See Interaction Protocol.

Output Format

See Interaction Protocol.

1 5

1

2

3

4

0

 
? 1 1

? 1 3

? 2 4

? 3 5

? 4 5

!
1 2
2 3
3 4
4 5

5 5

1

0

0

2

2

 
? 1 1

? 1 3

? 2 4

? 3 5

? 4 5

!
1 3
2 3
2 4
2 5

Hint

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