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

输入

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)$ 的一个排列
• 每个输入文件中所有 $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 翻译