CF1621C.Hidden Permutations

This is an interactive problem.

The jury has a permutation $p$ of length $n$ and wants you to guess it. For this, the jury created another permutation $q$ of length $n$. Initially, $q$ is an identity permutation ($q_i = i$ for all $i$).

You can ask queries to get $q_i$ for any $i$ you want. After each query, the jury will change $q$ in the following way:

• At first, the jury will create a new permutation $q'$ of length $n$ such that $q'_i = q_{p_i}$ for all $i$.
• Then the jury will replace permutation $q$ with pemutation $q'$.

You can make no more than $2n$ queries in order to quess $p$.

这是一个交互式问题。

评测组持有一个长度为 $n$ 的排列 $p$，并希望你猜出它。为此，评测组构造了另一个长度为 $n$ 的排列 $q$。初始时，$q$ 是一个恒等排列（即对所有 $i$，均有 $q_i = i$）。

你可以进行查询，以获取任意位置 $i$ 处的 $q_i$ 值。每次查询后，评测组将按如下方式更新 $q$：

• 首先，评测组构造一个新的长度为 $n$ 的排列 $q'$，使得对所有 $i$，均有 $q'_i = q_{p_i}$；
• 然后，评测组将排列 $q$ 替换为排列 $q'$。

你至多可以进行 $2n$ 次查询来猜出 $p$。

The first line of input contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

输入的第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。

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

Before the first query $q = [1, 2, 3, 4]$ so answer for the query will be $q_3 = 3$.

Before the second query $q = [4, 2, 1, 3]$ so answer for the query will be $q_2 = 2$.

Before the third query $q = [3, 2, 4, 1]$ so answer for the query will be $q_4 = 1$.

In the second test case the hidden permutation $p = [1, 3, 4, 2]$.

Empty strings are given only for better readability. There will be no empty lines in the testing system.

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

第一次查询前，$q = [1, 2, 3, 4]$，因此该查询的答案为 $q_3 = 3$。

第二次查询前，$q = [4, 2, 1, 3]$，因此该查询的答案为 $q_2 = 2$。

第三次查询前，$q = [3, 2, 4, 1]$，因此该查询的答案为 $q_4 = 1$。

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

空行仅用于提高可读性。评测系统中不会出现空行。