E. Tree Guessing
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Maozon - Stasis

This is an interactive problem.

The interactor has a hidden tree with $$$n$$$ vertices, numbered from $$$1$$$ to $$$n$$$. Your task is to find this tree using at most $$$2n - 2$$$ queries.

In each query, you choose a vertex $$$x$$$ and a permutation $$$p_1, p_2, \ldots, p_n$$$ of the integers from $$$1$$$ to $$$n$$$, and the interactor returns $$$$$$\sum_{i = 1}^{n} \max_{j \in \text{path}(i, x)} p_j,$$$$$$ where $$$\text{path}(i, x)$$$ is the set of vertices on the simple path between $$$i$$$ and $$$x$$$, including both $$$i$$$ and $$$x$$$ (in particular, $$$\text{path}(x, x) = \{x\}$$$).

In other words, for each vertex $$$i$$$, consider all vertices $$$j$$$ on the unique path from $$$i$$$ to $$$x$$$, including both endpoints, and take the largest $$$p_j$$$ among them. The interactor returns the sum of these maximum values over all $$$n$$$ vertices $$$i$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 250$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 500$$$) — the number of vertices in the tree.

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

Interaction

To make a query, output a line in the format "? $$$x\, p_1\, p_2\, \ldots\, p_n$$$" ($$$1 \le x \le n$$$, and $$$p_1, p_2, \ldots, p_n$$$ is a permutation of the integers from $$$1$$$ to $$$n$$$). After each query, read a single integer — the answer to the query. You can make at most $$$2n - 2$$$ queries in each test case.

When you have found the tree, output a line containing "!", followed by $$$n - 1$$$ lines, each containing two integers $$$u$$$ and $$$v$$$, meaning that there is an edge between vertices $$$u$$$ and $$$v$$$. You can output the edges in any order. Outputting the answer does not count as a query. After printing all edges of your answer, flush the output. After that, proceed to the next test case, or terminate the program if it was the last one.

The interactor is not adaptive, which means the tree is fixed in advance and does not change during the interaction.

After printing each query do not forget to output the end of line and flush$$$^{\text{∗}}$$$ the output. Otherwise, you will get Idleness limit exceeded verdict.

If, at any interaction step, you read $$$-1$$$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.

Hacks

To hack, use the following format.

The first line should contain a single integer $$$t$$$ ($$$1 \le t \le 250$$$) — the number of test cases.

The first line of each test case should contain a single integer $$$n$$$ ($$$2 \le n \le 500$$$) — the number of vertices in the tree.

Each of the next $$$n - 1$$$ lines should contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — an edge of the tree. The given edges must form a tree.

The sum of $$$n$$$ over all test cases should not exceed $$$500$$$.

$$$^{\text{∗}}$$$To flush, use:

  • fflush(stdout) or cout.flush() in C++;
  • sys.stdout.flush() in Python;
  • see the documentation for other languages.
Example
Input
6
2

3

6

7

4

10

13

4

10

11

13

16

8

10
Output
!
1 2

? 1 1 2 3

? 2 1 2 3

!
3 1
1 2

? 1 1 2 3 4

? 2 1 3 4 2

!
1 2
1 3
2 4

? 1 1 2 3 4

? 1 2 1 3 4

? 1 3 1 2 4

? 1 4 1 2 3

!
1 2
1 3
1 4

!
1 2
2 3
3 4
4 5
5 6
6 7
7 8

!
1 2
1 3
2 4
2 5
3 6
3 7
4 8
5 9
6 10
Note

In the first test case, the only possible tree on two vertices consists of the single edge $$$(1, 2)$$$, so no queries are needed. The answer is ! followed by this edge.

In the second test case, the tree has two edges, $$$(1, 2)$$$ and $$$(1, 3)$$$.

In the first query, $$$x = 1$$$ and $$$p = [1, 2, 3]$$$, so the interactor returns $$$\max\{1\} + \max\{2, 1\} + \max\{3, 1\} = 6$$$.

In the second query, $$$x = 2$$$ and $$$p = [1, 2, 3]$$$, so the interactor returns $$$\max\{1, 2\} + \max\{2\} + \max\{3, 1, 2\} = 7$$$.