[ARC167D] Good Permutation

对于一个 $(1,2,\ldots,N)$ 的排列 $Q$，称其是好的，当且仅当 - 对于每个整数 $i \in [1,N]$，在若干次 $i \gets Q_i$ 后能够得到 $i=1$。 给定一个排列 $P$，每次操作可以交换两个数。使用最小的操作次数，使得 $P$ 成为一个好的排列，若有多种解，输出字典序最小的。

[problemUrl]: https://atcoder.jp/contests/arc167/tasks/arc167_d この問題では順列と言った際には $ (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 $ 回以上行うことで、 $ P $ を良い順列にしたいです。 - $ 1\leq\ i\lt\ j\ \leq\ N $ を満たす整数 $ i,j $ を選んで、 $ P_{i} $ と $ P_{j} $ を入れ替える $ P $ を良い順列にするのに必要な最小の操作回数を $ M $ としたとき、 $ P $ に対し操作を $ M $ 回行うことで得られる良い順列のうち、辞書式順序で最小のものを求めてください。 $ 1 $ つの入力ファイルにつき $ T $ 個のテストケースが与えられるので、それぞれについて解いてください。 数列の辞書順とは？数列 $ S\ =\ (S_1,S_2,\ldots,S_{|S|}) $ が数列 $ T\ =\ (T_1,T_2,\ldots,T_{|T|}) $ より**辞書順で小さい**とは、下記の 1. と 2. のどちらかが成り立つことを言います。 ここで、$ |S|,\ |T| $ はそれぞれ $ S,\ T $ の長さを表します。 1. $ |S|\ \lt\ |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 $ が存在して、下記の $ 2 $ つがともに成り立つ。 - $ (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 $ 行目には $ \text{case}_{i} $ に対する答えの良い順列を空白区切りで出力してください。

5
4
2 1 4 3
5
2 1 3 4 5
2
1 2
2
2 1
9
4 3 6 2 7 1 9 8 5

2 3 4 1
2 3 4 5 1
2 1
2 1
4 3 5 2 7 1 8 9 6

### 制約 - $ 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) $ の順列 - $ 1 $ つの入力ファイルにつき、 $ N $ の総和は $ 2\times\ 10^{5} $ を超えない - 入力は全て整数 ### Sample Explanation 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 $ 回の操作で得られる良い順列のうち辞書順で最も小さいものになるため、これが答えです。