分数: 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 等于 1 通过重复替换 x\leftarrow Q_{x} 一些次。
你想要 P 通过执行以下操作得到一个好的排列 P 零次或多次。
- 选择整数 i 和 j 这样 1\leq i\lt j \leq N,并交换 P_{i} 和 P_{j}.
让 M 是必须执行该操作才能使 P 一个很好的排列。找到通过执行该操作可以获得的按字典顺序最小的好排列 M 次 P.
对于每个输入文件,您有 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 满足以下两项。
- (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).
- 对于每个输入文件,总和 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-th 行应包含作为答案的排列 \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
对于第一个测试用例:
P 不是一个好的排列。交换 P_{1} 和 P_{3} 使 P=(4,1,2,3),这是一个很好的排列,所以 M=1。 除此之外,交换 P_{2} 和 P_{4} 使 P=(2,3,4,1),这是按字典顺序可以获得的最小的好排列 M=1 操作,所以这就是答案。