题解

思路

建立每个顶点只有一条出边 $i\to p_i$ 的置换图，并把 $1$ 到 $N$ 染成红色，其余顶点染成蓝色。

做法

设连通分量数为 $K$，完全由红点组成且大小至少为二的环数为 $R$，完全由蓝点组成且大小至少为二的环数为 $B$。一次合法交换等价于在两个异色顶点处交换出边；每次至多让分量数向目标增加一，同时处理单色环还需要配对或借助另一颜色的分量。

由此可得最少操作数为 $N+M-K+2\max(R,B)$：先把红色单色环与蓝色单色环两两配对拆开，再让剩余单色环借助含另一颜色的分量，最后逐个拆开混色环即可达到该下界。

复杂度

一次遍历置换的所有环就能统计 $K,R,B$，时间复杂度 $O(N+M)$，空间复杂度 $O(N+M)$。