まず，\(P_N=N\) は明らかに必要です．

すると，\(N \in S\) になる \(S\) に関しては条件を必ず満たすので，それ以外の \(S\) を考えればよいです．

これは，グラフから \(N\) を削除して問題を解くことと同値です． グラフから \(N\) を削除した結果，複数の連結成分が現れたとします． すると，これらの連結成分ではそれぞれ独立に問題を解くことができます． このとき，\(P\) の値域として，\(1,2,\cdots,N-1\) が残っていますが，これをそれぞれの連結成分にどう分配するかで自由度があります． この自由度はコンビネーションの式で計算できます．

上記のプロセスをそのまま実装すると，グラフからの頂点削除が面倒です． そこでこれを逆順に行うことにすると，頂点 \(i\) を追加し，辺 \((i,j)\) \((j \leq i)\) を追加する，という操作になり，union-find で簡単に処理できる形になります．

計算量は全体で \(O(M \alpha(N))\) になります．ただしここで \(\alpha(N)\) はアッカーマン関数の逆関数です．

解答例(c++)