公式解説と同様、連結成分の大きさが全て \(S\) 以下になるような、条件を満たすグラフの種類数を数えます。

\(dp[n][m][rank] \coloneqq \) 頂点数 \(n\), 辺の個数 \(m\) で、各連結成分のランクが全て \(rank\) 以下になるようなグラフの総数 とした動的計画法を行います。
ここで、各連結成分について、以下のようにランクを定めています。

• 連結成分がサイズ \(k\) のパスの時→ \(2k - 2\)
• 連結成分がサイズ \(k\) のサイクルの時 → \(2k - 3\)

よって、ランクが小さい順に、孤立点, サイズ \(2\) のサイクル, サイズ \(2\) のパス, サイズ \(3\) のサイクル, … となります。

遷移については、ランクが \(rank\) の連結成分を作る個数で場合分けすることで、
\(rank\) が 0 の時、\(m = 0\) であれば \(dp[n][m][rank] = 1\), そうでなければ \(dp[n][m][rank] = 0\) です。

\(rank\) が 1 の時、サイズ \(2\) のサイクルで、

\[ dp[n][m][rank] = \sum_{n - ak \geq 0, m - ak \geq 0} dp[n - ak] [m - ak][rank - 1] \cdot \frac{n!}{2^aa!(n - ak)!} \]

\(rank\) が2以上の偶数の時、サイズ \(k = rank / 2 + 1\) のパスで、

\[ dp[n][m][rank] = \sum_{n - ak \geq 0, m - a(k-1) \geq 0} dp[n - ak] [m - a(k-1)][rank - 1] \cdot \frac{n!}{2^{a}a!(n - ak)!} \]

\(rank\) が3以上の奇数の時、サイズ \(k = \lceil rank / 2 \rceil + 1\) のサイクルで、

\[ dp[n][m][rank] = \sum_{n - ak \geq 0, m - ak \geq 0} dp[n - ak][m - ak][rank - 1] \cdot \frac{n!}{2^a k^a a!(n - ak)!} \]

です。
遷移の総数は、調和級数を用いて、全体で \(O(NML\log \min(N, M))\) であることがわかります。
係数の部分は適当に前計算をして\(O(1)\) で計算でき、全体で \(O(NML\log \min(N, M))\) で計算できました。

実装例