Hidden Permutations

题意翻译

**这是一道 I/O 交互题。** Jury 有一个长度为 $n$ 的排列 $p$，想让你通过若干次询问猜出来。为此，Jury 新建了一个长度为 $n$ 的排列 $q$，并且初始时，$\forall i\in[1,n]$，$q_i=i$。 你在每次询问中可以向 Jury 询问排列 $q$ 中位置 $i(1\leqslant i\leqslant n)$ 上的数的值，即 $q_i$。每次询问后，Jury 会执行如下操作： - 新建一个排列 $q'$，其中 $q'_i=q_{p_i}$。 - 将排列 $q$ 替换为排列 $q'$。 现在，请你通过至多 $2n$ 次询问求出这个数列。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 1000$。 - $1\leqslant n,\sum n\leqslant 10^4$。 Translated by Eason_AC 2022.1.4

题目描述

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 $ .

输入输出格式

输入格式

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

输出格式

Interaction in each test case starts after reading the single integer $ n $ ( $ 1 \leq n \leq 10^4 $ ) — the length of permutations $ p $ and $ q $ . To get the value of $ q_i $ , output the query in the format $ ? $ $ i $ ( $ 1 \leq i \leq n $ ). After that you will receive the value of $ q_i $ . You can make at most $ 2n $ queries. After the incorrect query you will receive $ 0 $ and you should exit immediately to get Wrong answer verdict. When you will be ready to determine $ p $ , output $ p $ in format $ ! $ $ p_1 $ $ p_2 $ $ \ldots $ $ p_n $ . After this you should go to the next test case or exit if it was the last test case. Printing the permutation is not counted as one of $ 2n $ queries. After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use: - fflush(stdout) or cout.flush() in C++; - System.out.flush() in Java; - flush(output) in Pascal; - stdout.flush() in Python; - see documentation for other languages. It is guaranteed that the sum of $ n $ over all test cases doesn't exceed $ 10^4 $ . The interactor is not adaptive in this problem. Hacks: To hack, use the following format: The first line contains the single integer $ t $ — the number of test cases. The first line of each test case contains the single integer $ n $ — the length of the permutations $ p $ and $ q $ . The second line of each test case contains $ n $ integers $ p_1, p_2, \ldots, p_n $ — the hidden permutation for this test case.

输入输出样例

输入样例 #1

2
4

3

2

1

4

2

4

4

输出样例 #1

? 3

? 2

? 4

! 4 2 1 3

? 2

? 3

? 2

! 1 3 4 2

说明

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.