公式解説とだいたい同じですが，辺についても指数型の母関数を考え，2 部グラフに「単純」という条件を課すことなく考察しています．

---

同タイミングで執筆されたこのユーザー解説は，途中まで私の解説と同じ．さらに私の解説から計算量を落とす方法にも触れられています．

https://atcoder.jp/contests/abc327/editorial/7592

---

ある種類のグラフに対して \(n\) 頂点 \(m\) 辺からなるラベル付きグラフ（頂点にも辺にもラベルがある）の数え上げが \(a_{n,m}\) であるとき，\(\sum_{n,m}a_{n,m}\dfrac{1}{n!}\dfrac{1}{m!}x^ny^m\) というタイプの母関数を考えることにします．

本問の設定に合わせて，グラフはループや多重辺を持つことを許容しておきます．次のグラフの母関数を考えます．

• 2 部グラフ：\(A(x,y)\)
• 連結 2 部グラフ：\(B(x,y)\)
• 色付き 2 部グラフ：\(C(x,y)\)
• 色付き連結 2 部グラフ：\(D(x,y)\)

ただし，色付き 2 部グラフとは，グラフ \(G\) および頂点集合の分割の方法 \(V(G) = V_1\amalg V_2\) の組 \((G,V_1,V_2)\) であって \(V_1\), \(V_2\) がそれぞれ独立集合であるものを指します．

単に \(2\) 部グラフと言った場合には「 \(V(G) = V_1\amalg V_2\) と分割する方法が存在する」というだけで，そのような分割方法は一般には一意ではないので，これらは異なる概念です（例えば \(1\) 頂点 \(0\) 辺の 2 部グラフはひとつ，\(1\) 頂点 \(0\) 辺の色付き 2 部グラフは 2 つあります）．

目標は \(N!M![x^Ny^M]A(x,y)\) の計算です．

\(A,B,C,D\) には次の関係があります．

• \(A = \exp B\), \(C = \exp D\)．
• \(B = \frac12 D\)

\(A = \exp(B)\) は，\(A\) の連結成分の個数がちょうど \(k\) 個である場合が \(\frac{B^k}{k!}\) になることからその総和として分かります（名前 \(1,2,\ldots,k\) の連結成分を作る方法が \(B^k\) であることを経由すると理解しやすいと思います）．また https://atcoder.jp/contests/abc318/tasks/abc318_h でも解説されています．

\(C=\exp D\) は同様です．

\(B = \frac12 D\) は，連結 2 部グラフの頂点を 2 色彩色する方法がちょうど \(2\) 通りあることから分かります．

したがって \(A = \sqrt{C}\) なので，\(C\) を求めて sqrt をとるという手順で答を計算できます．

---

\(A,B,C,D\) のうちでは \(C(x,y)\) が最も考察が簡単でしょう．\(n\) 頂点のうち色 \(1\) の頂点が \(n_1\) 個，色 \(2\) の頂点が \(n_2\) 個あるときのことを考えると，数え上げ \(c_{n,m}\) は

\[c_{n,m} = \sum_{n_1+n_2=n}\binom{n}{n_1}(n_1n_2)^m\]

となることが分かります．よって

\[C(x,y) = \sum_{n}\biggl(\sum_{n_1+n_2=n}\frac{1}{n_1!}\frac{1}{n_2!}\exp(n_1n_2y)\biggr)x^n\]

と書けます．

---

あとは答を計算する方法を考えます．

\(C(x,y) = \sum_n {c_n(y)x^n}\) と書きます．\(A^2=C\) であるときに \(A(x,y) = \sum_{n}a_n(y)x^n\) を求める方法を考えればよいです．

\(y\) を忘れてた単に \(A(x)^2=C(x)\) という関係式を考えると行うべき計算が分かりやすいでしょう． \(\sum_{i+j=n}a_ia_j = c_n\) から，昇順に \(a_n = \dfrac12(c_n - \sum_{i+j=n, i,j>0}a_ia_j)\) という要領で計算できます．

係数の積を求める計算を全部で \(O(N^2)\) 回行えばよさそうです．

係数 \(c_n(y)\) がどのような形式的べき級数だったかを思い出すと，\(c_n(y) = \sum c_{n,k}\exp (ky)\) と書けるのでした．そのような形式的べき級数同士の和や積も同様の形を持つので，このような形の式を適切に管理すればよいです．

最後に，\(a_{n,k}\exp (ky)x^n\) の答えへの寄与は \(N!a_{n,k}(2k)^M\) であることから答が計算できます．

以上により本問題を \(O(N^6+N^4\log M)\) 時間で解くことができます．