求める答えを \(C\) とします。
\(i=1,2,\dots,N\) に対して \(Q_{P_i}=i\) となるように \(Q\) を定義します。 \(1,2,\dots,N\) に対して \(f(i)\) を以下で再帰的に定義します。

• \(f(1)=1\)
• \(i \geq 2\) のとき、以下の条件を満たす \(1\) 以上 \(N\) 以下の整数 \(j\) が存在するならば \(f(i)=f(i-1)+1\)、存在しないならば \(f(i)=f(i-1)\)
  • 頂点 \(Q_j\) から頂点 \(Q_i\) に有向辺をたどって到達することができる
  • \(f(j)=f(i-1)\)

\(C=N-f(N)\) を証明します。

高橋君は、\(f(i)=f(i-1)\) となる \(i\) \((2 \leq i \leq N)\) について、\(P_{Q_i}=i\) であることを青木君に伝えることにします。このとき、高橋君は青木君に \(N-f(N)\) 個の要素を伝えることになります。 伝えられた条件を満たす特別な順列が \(P\) 以外に存在すると仮定し、それを \(P'\) とします。 \(P\neq P'\) であることから、

• \(f(k) = f(k-1)+1\)
• \(k>P'_{Q_k}\)

となる \(k\) が存在します。 これらを満たす \(k\) のうち最小のものを取ってきます。 \(f\) の定義より、以下を満たす \(k'\) が存在します。

• \(k'<k\)
• \(f(k')=f(k)-1\)
• 頂点 \(Q_{k'}\) から頂点 \(Q_k\) に有向辺をたどって到達することができる

\(k'+1,k'+2,\dots,k-1\) の位置は青木君に伝えられるため、\(k' \geq P'_{Q_k}\) です。 また、\(3\) つ目の条件と \(P'\) が特別な順列であることより、 \(P'_{Q_{k'}}<P'_{Q_k}\) です。

\(k'\) の位置が青木君に伝えられていないとき、\(f(k')=f(k'-1)+1\) なので、\(k\) の最小性より \(k' \leq P'_{Q_{k'}}\) です。 このとき、\(k' \leq P'_{Q_{k'}}<P'_{Q_k} \leq k'\) となって矛盾します。
\(k'\) の位置が青木君に伝えられているとき、\(k'=P'_{Q_{k'}}<P'_{Q_k} \leq k'\) となって矛盾します。
よって、そのような \(P'\) は存在せず、青木君は \(P\) を一意に特定できることから、\(C \leq N-f(N)\) がわかります。

高橋君が \(N-f(N)\) 個未満の項を青木君に伝えたとします。 このとき、鳩ノ巣原理により、以下を満たす \(i_1,i_2\) が存在します。

• \(f(P_{i_1})=f(P_{i_2})\)
• \(P_{i_1}\) と \(P_{i_2}\) は高橋君から青木君に伝えられない

このとき、青木君にとっては \(P_{i_1}\) と \(P_{i_2}\) を区別できず、\(P\) の各項を特定できません。 よって、\(C \geq N-f(N)\) です。

以上により、\(C=N-f(N)\) が証明できました。 \(f\) を定義に従って求めていくことで、この問題を \(O(N+M)\) で解くことができます。