\(i \rightarrow p_i\) で辺を張った有向グラフを考えましょう。 頂点 \(1,\ldots, N\) を赤く、頂点 \(N+1,\ldots,N+M\) を青く塗ります。

結論から言えば、このグラフにおける連結成分の個数を \(K\)、赤色の頂点のみからなるサイズ \(2\) 以上の連結成分の個数を \(R\)、青色の頂点のみからなるサイズ \(2\) 以上の連結成分の個数を \(B\) として、答えは \(N+M-K+2 \max(R,B)\) です。これは時間計算量 \(O(N+M)\) で実行可能で十分高速です。

以降はこれの正当性を示します。

まず、もとの問題における操作は色が異なる頂点 \(i,j\) を選び以下の \(4\) つの処理を行うことと対応しています。

• 辺 \(i \rightarrow p_i\) を取り除く
• 辺 \(j \rightarrow p_j\) を取り除く
• 辺 \(i \rightarrow p_j\) を追加する
• 辺 \(j \rightarrow p_i\) を追加する

操作の結果、新たにできるグラフの連結成分の個数は \(i,j\) が同じ連結成分に属していたならば \(1\) 増加し、そうでなければ \(1\) 減少します。

\(N+M-K+2 \max(R,B)\) が操作回数の下限であることを示します。\(K_i,R_i,B_i\) を以下のように定義します。目標は \(K_n = N+M,R_n = 0, B_n=0\) とできる最小の \(n\) を求めることです。

• \(K_i\)：\(i\) 回目の操作を終えた時点での連結成分の個数
• \(R_i\)：\(i\) 回目の操作を終えた時点での赤色の頂点のみからなるサイズ \(2\) 以上の連結成分の個数
• \(B_i\)：\(i\) 回目の操作を終えた時点での青色の頂点のみからなるサイズ \(2\) 以上の連結成分の個数

操作の性質から \(|K_{i+1} - K_i| =1, |R_{i+1} - R_{i}| \leq 1, |B_{i+1} - B_{i}| \leq 1\) を満たす必要があります。さらに \(R_{i+1} - R_{i} =1\) とできるのは \(K_{i+1} - K_i = 1\) の場合に限られます。同様に \(R_{i+1} - R_{i} =-1\) とできるのは \(K_{i+1} - K_i = -1\) の場合に限られます。\(B_i\) についても同様です。

このとき \(f(i) = i+N+M-K_i + 2 \max(R_i,B_i)\) として、\(f(i) \leq f(i+1)\) となることが証明できます。ここから \(N+M-K_0+2 \max(R_0,B_0)\) が操作回数の下限であることが言えます。

以下の貪欲法により、実際に上記の下限を達成可能です。

1. 以下を可能な限り繰り返す
   • 赤色の頂点のみ、青色の頂点のみからなるサイズ \(2\) 以上の連結成分がともに存在したなら、その連結成分間で \(1\) 度操作を行う。
2. 以下を可能な限り繰り返す
   • 赤色の頂点のみからなるサイズ \(2\) 以上の連結成分が存在したなら、青色の頂点を含むような連結成分を自由に選びその連結成分間で \(1\) 度操作を行う。
3. 以下を可能な限り繰り返す
   • 青色の頂点のみからなるサイズ \(2\) 以上の連結成分が存在したなら、赤色の頂点を含むような連結成分を自由に選びその連結成分間で \(1\) 度操作を行う。
4. 以下を可能な限り繰り返す
   • \(i,p_i\) の色が異なるような \(i\) であって、操作の結果単色の頂点のみからなるサイズ \(2\) 以上の連結成分ができないような \(i\) を選び、\(i,p_i\) について操作を行う(そのような \(i\) は必ず存在する)。