AT_arc167_d [ARC167D] Good Permutation

在本题中，提到“顺序”时，指的是 $ (1,2,\dots,N) $ 的一个排列。 给定一个排列 $ P=(P_{1},P_{2},\dots,P_{N}) $。 我们将满足以下条件的排列 $ Q=(Q_{1},Q_{2},\dots,Q_{N}) $ 称为“好排列”： - 对于任意整数 $ 1\leq x\leq N $，通过任意次执行 $ x\leftarrow Q_{x} $ 这个替换操作，可以将 $ x $ 变为 $ 1 $。 你可以对 $ P $ 进行如下操作若干次（可以为 $ 0 $ 次），使其变为一个好排列： - 选择满足 $ 1\leq i

输入从标准输入读入，格式如下： > $ T $ $ \text{case}_{1} $ $ \text{case}_{2} $ $ \vdots $ $ \text{case}_{T} $ 每组测试数据格式如下： > $ N $ $ P_{1} $ $ P_{2} $ $ \cdots $ $ P_{N} $

请输出 $ T $ 行，第 $ i $ 行输出第 $ i $ 组测试数据的答案，即字典序最小的好排列，数之间用空格分隔。

### 数据范围 - $ 1\leq T\leq 10^{5} $ - $ 2\leq N\leq 2\times 10^{5} $ - $ (P_{1},P_{2},\dots,P_{N}) $ 是 $ (1,2,\dots,N) $ 的一个排列 - 每个输入文件中所有 $ N $ 的总和不超过 $ 2\times 10^{5} $ - 输入均为整数 ### 样例解释 1 对于第 1 组测试数据，$ P $ 不是好排列。将 $ P_{1} $ 与 $ P_{3} $ 交换后，$ P=(4,1,2,3) $，此时 $ P $ 是好排列，$ M=1 $。另外，将 $ P_{2} $ 与 $ P_{4} $ 交换后，$ P=(2,3,4,1) $，这是用 $ M=1 $ 次操作得到的好排列中字典序最小的，因此答案为该排列。 由 ChatGPT 4.1 翻译