\(N\) 頂点で、 \(N\) 本の辺 \((i,P_{i})\) が存在するグラフ \(G\) とします。\(P\) が変化すると \(G\) も変化することとします。

連結成分の個数を \(C\) とすると、 \(P\) が良い順列なら \(C=1\) となります。\(C\neq 1\) のとき、 \(P_{i},P_{j}\) を入れ替えることで \(C\) がちょうど \(1\) 減るような \(i,j\) が存在することから、 \(M=C-1\) となります。

\(i=1,2,\dots N\) の順に以下を行えばいいです。

• \(P_{i}=a\) となる、操作の数が \(M\) 回で達成可能な良い順列が存在する \(a\) のうち、最も最小のものをとる。そして、 \(P_{i}\neq a\) であるなら、整数 \(b\) を \(b=P_{a}\) を満たすものとして、 \(P_{i},P_{b}\) を入れ替え、\(M\) を \(1\) 減らす。

ここで、 \(a\) として選ばれるのは \(P_{i}\) もしくは以下のように定義される \(r\) です。

• \(G\) の頂点 \(j-1,j\) が異なる連結成分に属している \(2\leq j\leq N\) のうち、最小の整数

\(a\) として \(r\) が選ばれるのは以下の \(2\) つの条件のいずれかが満たされるときのみです。

• \(r\lt P_{i}\)
• \(i=r-1\) かつ \(1\leq j\leq i\) を満たす全ての整数 \(j\) に対して \(P_{j}\lt r\) が成り立つ。

よって、 \(M\) が \(1\) 減るたびに \(a\) を求めた後、上記の \(2\) つの条件のいずれかを満たす最小の \(i\) を計算すれば良いです。

\(i\) は単調増加でかつ \(a\) も単調増加であることを活かした実装をすると時間計算量 \(O(N)\) や \(O(N\alpha (N))\) で計算することができます。