CF1621C Hidden Permutations

这是一个交互题。 评测器有一个长度为 $n$ 的排列 $p$，你需要猜出它。为此，评测器还创建了另一个长度为 $n$ 的排列 $q$。初始时，$q$ 是一个恒等排列（即 $q_i = i$ 对所有 $i$ 成立）。 你可以进行若干次询问，询问任意 $i$ 的 $q_i$ 值。每次询问后，评测器会按如下方式修改 $q$： - 首先，评测器会创建一个新的排列 $q'$，其中 $q'_i = q_{p_i}$ 对所有 $i$ 成立。 - 然后，评测器用 $q'$ 替换 $q$。 你最多可以进行 $2n$ 次询问来猜出 $p$。

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

每个测试用例的交互从读取一个整数 $n$（$1 \leq n \leq 10^4$）开始，表示排列 $p$ 和 $q$ 的长度。 为了获得 $q_i$ 的值，你需要输出形如 $?$ $i$（$1 \leq i \leq n$）的询问。之后你会收到 $q_i$ 的值。 你最多可以进行 $2n$ 次询问。如果你进行了非法的询问，你会收到 $0$ 作为回复，此时应立即退出，否则会被判为 Wrong answer。 当你准备好输出 $p$ 时，输出 $!$ $p_1$ $p_2$ $\ldots$ $p_n$。输出排列不计入 $2n$ 次询问次数。 每次输出后不要忘记换行并刷新输出缓冲区，否则会被判为 Idleness limit exceeded。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 保证所有测试用例中 $n$ 的总和不超过 $10^4$。交互器在本题中是非自适应的。 Hack 格式： 第一行包含一个整数 $t$，表示测试用例数量。 每个测试用例的第一行包含一个整数 $n$，表示排列 $p$ 和 $q$ 的长度。第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$，表示本测试用例的隐藏排列。

在第一个测试用例中，隐藏排列 $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]$。 空行仅用于更好的可读性，评测系统中不会有空行。 由 ChatGPT 4.1 翻译