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<j\leq N $ 的整数 $ i,j $，交换 $ P_{i} $ 和 $ P_{j} $。

设将 $ P $ 变为好排列所需的最小操作次数为 $ M $，请你在对 $ P $ 进行 $ M $ 次操作后，输出所有可能得到的好排列中字典序最小的一个。

一个输入文件包含 $ T $ 组测试数据，请分别求解。

数列的字典序定义如下：设 $ S=(S_1,S_2,\ldots,S_{|S|}) $，$ T=(T_1,T_2,\ldots,T_{|T|}) $，$ |S|,|T| $ 分别表示 $ S,T $ 的长度。$ S $ 字典序小于 $ T $ 当且仅当满足以下两条之一：

1. $ |S|<|T| $ 且 $ (S_1,S_2,\ldots,S_{|S|})=(T_1,T_2,\ldots,T_{|S|}) $。
2. 存在整数 $ 1\leq i\leq \min\lbrace |S|,|T| \rbrace $，使得以下两点都成立：
   • $ (S_1,S_2,\ldots,S_{i-1})=(T_1,T_2,\ldots,T_{i-1}) $
   • $ S_i $ 小于 $ T_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 翻译