Tree GuessingAI (CI翻译)
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.
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$.
{"titleZh":"猜树","bodyZh":"$n$ 个顶点的树，顶点编号为 $1$ 到 $n$。你的任务是使用不超过 $2n - 2$ 次询问找出这棵树。\n\n在每次询问中，你需要选择一个顶点 $x$ 和一个由 $1$ 到 $n$ 的整数构成的排列 $p_1, p_2, \ldots, p_n$，交互器将返回 $$\\sum_{i = 1}^{n} \\max_{j \\in \\text{path}(i, x)} p_j,$$ 其中，$\\text{path}(i, x)$ 表示 $i$ 和 $x$ 之间的简单路径上的顶点集合，包括 $i$ 和 $x$（特别地，$\\text{path}(x, x) = \\{x\\}$）。\n\n换句话说，对于每个顶点 $i$，考虑从 $i$ 到 $x$ 的唯一路径上的所有顶点（包括两个端点），取其中最大的 $p_j$。交互器返回所有 $n$ 个顶点 $i$ 对应的最大值之和。\n\n## 输入格式\n\n每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \\le t \\le 250$）。接下来是各测试用例的描述。\n\n每个测试用例的第一行包含一个整数 $n$（$2 \\le n \\le 500$）——树中的顶点数。\n\n保证所有测试用例的 $n$ 之和不超过 $500$。\n\n## 交互\n\n进行询问时，输出一行，格式为 "? $x\\, p_1\\, p_2\\, \\ldots\\, p_n$"（$1 \\le x \\le n$，且 $p_1, p_2, \\ldots, p_n$ 是由 $1$ 到 $n$ 构成的排列）。每次询问后，读取一个整数——该询问的答案。每个测试用例最多可以进行 $2n - 2$ 次询问。\n\n当你找到这棵树后，输出一行，其中包含 "!"，随后输出 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$，表示顶点 $u$ 和顶点 $v$ 之间存在一条边。边可以按任意顺序输出。输出答案不计入询问次数。输出答案中的所有边后，刷新输出。之后继续处理下一个测试用例；如果这是最后一个测试用例，则终止程序。\n\n交互器*不是自适应的，这意味着树会预先固定，并且在交互过程中不会改变。\n\n输出每次询问后，不要忘记输出换行并刷新$^{\\text{∗}}$输出。否则，你将收到 Idleness limit exceeded 判定。\n\n如果在交互的任意步骤中，读取到 $-1$ 而不是有效数据，你的程序必须立即退出。这意味着由于询问无效或其他错误，你的程序将收到 Wrong answer。如果不退出，程序继续从已关闭的输入流中读取，可能会得到任意判定。\n\n提交测试数据（Hacks）\n\n进行 hack 时，请使用以下格式。\n\n第一行应包含一个整数 $t$（$1 \\le t \\le 250$）——测试用例的数量。\n\n每个测试用例的第一行应包含一个整数 $n$（$2 \\le n \\le 500$）——树中的顶点数。\n\n接下来的 $n - 1$ 行中，每行应包含两个整数 $u$ 和 $v$（$1 \\le u, v \\le n$，$u \\ne v$）——树的一条边。给出的边必须构成一棵树。\n\n所有测试用例的 $n$ 之和不应超过 $500$。\n\n$^{\\text{∗}}$刷新输出的方法：在 C++ 中使用 fflush(stdout) 或 cout.flush()；在 Python 中使用 sys.stdout.flush()；其他语言请参阅相关文档。\n\n## 说明\n\n在第一个测试用例中，两个顶点的树只有一种可能，即包含一条边 $(1, 2)$，因此不需要进行询问。答案为 !，后跟这条边。\n\n在第二个测试用例中，这棵树包含两条边 $(1, 2)$ 和 $(1, 3)$。\n\n第一次询问中，$x = 1$ 且 $p = [1, 2, 3]$，因此交互器返回 $\\max\\{1\\} + \\max\\{2, 1\\} + \\max\\{3, 1\\} = 6$。\n\n第二次询问中，$x = 2$ 且 $p = [1, 2, 3]$，因此交互器返回 $\\max\\{1, 2\\} + \\max\\{2\\} + \\max\\{3, 1, 2\\} = 7$。\n
样例
6
2
3
6
7
4
10
13
4
10
11
13
16
8
10
!
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
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。