CF1815B.Sum Graph

This is an interactive problem.

There is a hidden permutation $p_1, p_2, \dots, p_n$.

Consider an undirected graph with $n$ nodes only with no edges. You can make two types of queries:

1. Specify an integer $x$ satisfying $2 \le x \le 2n$. For all integers $i$ ($1 \le i \le n$) such that $1 \le x-i \le n$, an edge between node $i$ and node $x-i$ will be added.
2. Query the number of edges in the shortest path between node $p_i$ and node $p_j$. As the answer to this question you will get the number of edges in the shortest path if such a path exists, or $-1$ if there is no such path.

Note that you can make both types of queries in any order.

Within $2n$ queries (including type $1$ and type $2$), guess two possible permutations, at least one of which is $p_1, p_2, \dots, p_n$. You get accepted if at least one of the permutations is correct. You are allowed to guess the same permutation twice.

A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

这是一个交互式问题。

存在一个隐藏的排列 $p_1, p_2, \dots, p_n$。

考虑一个包含 $n$ 个节点但没有边的无向图。你可以执行以下两种类型的查询：

1. 指定一个满足 $2 \le x \le 2n$ 的整数 $x$。对于所有满足 $1 \le x-i \le n$ 的整数 $i$（其中 $1 \le i \le n$），在节点 $i$ 和节点 $x-i$ 之间添加一条边。
2. 查询节点 $p_i$ 与节点 $p_j$ 之间最短路径所含的边数。若该路径存在，你将得到该最短路径的边数；否则返回 $-1$。

注意：你可以以任意顺序执行这两种类型的查询。

在总共不超过 $2n$ 次查询（包括类型 1 和类型 2 的查询）内，猜出两个可能的排列，其中至少有一个是 $p_1, p_2, \dots, p_n$。只要其中一个排列正确，即视为通过。允许两次猜测相同的排列。

长度为 $n$ 的排列是指由 $1$ 到 $n$ 中互不相同的 $n$ 个整数组成的任意顺序的数组。例如，$[2,3,1,5,4]$ 是一个排列，而 $[1,2,2]$ 不是排列（数字 $2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中出现了 $4$）。

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 10^3$) — the length of the permutation.

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

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 100$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^3$）—— 排列的长度。

保证所有测试用例的 $n$ 之和不超过 $10^3$。

In the first test case, $n=6$ and the hidden permutation $p = [1,4,2,5,3,6]$.

Firstly, make a type $1$ query on $x=12, 2, 3$ respectively. This adds four edges to the graph in total:

• An edge that connects node $6$ and node $6$.
• An edge that connects node $1$ and node $1$.
• An edge that connects node $1$ and node $2$.
• An edge that connects node $2$ and node $1$.

Since all of these queries are valid, the interactor returns $1$ after each of them.

Then, query the number of edges in the shortest path between node $p_1 = 1$ and $p_3 = 2$, which is equal to $1$.

Then, make a type $1$ query on $x=5$. This adds four edges to the graph in total:

• An edge that connects node $1$ and node $4$.
• An edge that connects node $2$ and node $3$.
• An edge that connects node $3$ and node $2$.
• An edge that connects node $4$ and node $1$.

Since this query is valid, the interactor returns $1$.

Then, query the number of edges in the shortest path between node $p_1 = 1$ and $p_5 = 3$, which is equal to $2$.

Then, query the number of edges in the shortest path between node $p_4 = 5$ and $p_5 = 3$. Such a path doesn't exist, therefore the interactor returns $-1$.

Afterwards, due to some magic, two possible permutations that can be $p$ are determined: the first permutation is $[1,4,2,5,3,6]$ and the second permutation is $[1,2,3,4,5,6]$. Since the first permutation is equal to the hidden permutation, this test case is solved correctly. In total, $7$ queries are used, which is within the limit of $2 \cdot 6 = 12$ queries.

Since the answer is correct, the interactor returns $1$.

In the second test case, $n=2$ and the hidden permutation is $p = [2,1]$.

Since there are only $2! = 2$ possible permutations, no queries are needed. It is sufficient to just output the two permutations, $[1,2]$ and $[2,1]$. In total, $0$ queries are used, which is within the limit of $2 \cdot 2 = 4$ queries.

Since the answer is correct, the interactor returns $1$.

在第一个测试用例中，$n=6$，隐藏排列为 $p = [1,4,2,5,3,6]$。

首先，分别对 $x=12, 2, 3$ 执行类型 $1$ 的查询。这总共向图中添加了四条边：

• 连接节点 $6$ 与节点 $6$ 的一条边。
• 连接节点 $1$ 与节点 $1$ 的一条边。
• 连接节点 $1$ 与节点 $2$ 的一条边。
• 连接节点 $2$ 与节点 $1$ 的一条边。

由于所有这些查询均合法，交互器在每次查询后均返回 $1$。

接着，查询节点 $p_1 = 1$ 与 $p_3 = 2$ 之间最短路径的边数，结果为 $1$。

然后，对 $x=5$ 执行类型 $1$ 的查询。这总共向图中添加了四条边：

• 连接节点 $1$ 与节点 $4$ 的一条边。
• 连接节点 $2$ 与节点 $3$ 的一条边。
• 连接节点 $3$ 与节点 $2$ 的一条边。
• 连接节点 $4$ 与节点 $1$ 的一条边。

由于该查询合法，交互器返回 $1$。

接着，查询节点 $p_1 = 1$ 与 $p_5 = 3$ 之间最短路径的边数，结果为 $2$。

然后，查询节点 $p_4 = 5$ 与 $p_5 = 3$ 之间最短路径的边数。这样的路径不存在，因此交互器返回 $-1$。

之后，借助某种“魔法”，确定出两个可能作为 $p$ 的排列：第一个排列是 $[1,4,2,5,3,6]$，第二个排列是 $[1,2,3,4,5,6]$。由于第一个排列恰好等于隐藏排列，该测试用例被正确解决。总共使用了 $7$ 次查询，未超过查询次数限制 $2 \cdot 6 = 12$。

由于答案正确，交互器返回 $1$。

在第二个测试用例中，$n=2$，隐藏排列为 $p = [2,1]$。

由于仅有 $2! = 2$ 种可能的排列，无需进行任何查询。只需直接输出两个排列 $[1,2]$ 和 $[2,1]$ 即可。总共使用了 $0$ 次查询，未超过查询次数限制 $2 \cdot 2 = 4$。

由于答案正确，交互器返回 $1$。