/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
この問題では順列と言った際には (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 の長さを表します。
- |S| \lt |T| かつ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})。
- ある整数 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 より（数として）小さい。
制約
- 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} を超えない
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
T
\text{case}_{1}
\text{case}_{2}
\vdots
\text{case}_{T}
各ケースは以下の形式で与えられます。
N
P_{1} P_{2} \cdots P_{N}
出力
T 行出力してください。 i 行目には \text{case}_{i} に対する答えの良い順列を空白区切りで出力してください。
入力例 1
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
出力例 1
2 3 4 1 2 3 4 5 1 2 1 2 1 4 3 5 2 7 1 8 9 6
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 回の操作で得られる良い順列のうち辞書順で最も小さいものになるため、これが答えです。
Score : 700 points
Problem Statement
In this problem, when we say just a "permutation", it refers to a permutation of (1,2,\dots,N).
You are given a permutation P=(P_{1},P_{2},\dots,P_{N}).
A permutation Q=(Q_{1},Q_{2},\dots,Q_{N}) is said to be a good permutation when the following holds.
- For every integer 1\leq x\leq N, it is possible to make x equal 1 by repeating the substitution x\leftarrow Q_{x} some number of times.
You want to make P a good permutation by performing the following operation on P zero or more times.
- Choose integers i and j such that 1\leq i\lt j \leq N, and swap P_{i} and P_{j}.
Let M be the minimum number of times you must perform the operation to make P a good permutation. Find the lexicographically smallest good permutation that can be obtained by performing the operation M times on P.
For each input file, you have T test cases to solve.
What is lexicographical order on sequences?
A sequence S = (S_1,S_2,\ldots,S_{|S|}) is said to be lexicographically smaller than a sequence T = (T_1,T_2,\ldots,T_{|T|}) when one of the following 1. or 2. holds. Here, |S| and |T| denote the lengths of S and T, respectively.
- |S| \lt |T| and (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
- There is an integer 1 \leq i \leq \min\lbrace |S|, |T| \rbrace that satisfies both of the following.
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1}).
- S_i is smaller than T_i (as a number).
Constraints
- 1\leq T\leq 10^{5}
- 2\leq N\leq 2\times 10^{5}
- (P_{1},P_{2},\dots ,P_{N}) is a permutation of (1,2,\dots ,N).
- For each input file, the sum of N does not exceed 2\times 10^{5}.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_{1}
\text{case}_{2}
\vdots
\text{case}_{T}
Each case is given in the following format:
N
P_{1} P_{2} \cdots P_{N}
Output
Print T lines. The i-th line should contain the permutation that is the answer for \text{case}_{i}, separated by spaces.
Sample Input 1
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
Sample Output 1
2 3 4 1 2 3 4 5 1 2 1 2 1 4 3 5 2 7 1 8 9 6
For the first test case:
P is not a good permutation. Swapping P_{1} and P_{3} makes P=(4,1,2,3), which is a good permutation, so M=1. Other than that, swapping P_{2} and P_{4} makes P=(2,3,4,1), which is the lexicographically smallest good permutation that can be obtained in M=1 operation, so this is the answer.