\(n\) 頂点 \(m\) 辺の単純連結二部グラフの数え上げを考えます．

ある単純連結グラフ \(G\) が二部グラフであることは以下と同値です．

• 頂点 \(1\) から各頂点までの距離を考える．このとき，同じ距離にあるような頂点同士の間に辺が存在しない（BFS 木において，同じ深さの頂点同士の間には辺が存在しない）

これをもとに dp をします． \(\mathrm{dp}[rem][prev][m]\) で「 BFS 木における親（の集合）がまだ決まっていない頂点の個数を \(rem\)，すでに決定した頂点のうち深さが最も深いものの個数を \(prev\)，すでに決定した辺の本数を \(m\)」とするような状態を持つと良いです．遷移は，次の深さの頂点集合を決めてそれぞれにの頂点ついて親の集合を考えることになります．（ABC281G の解説と状態の持ち方や遷移が似ているので参考にしてください．）

計算量は各 \(n\) に対して \(O(n^5 \log n)\) 程度となりますが，定数倍が軽く高速に動作します．

\(n\) 頂点 \(m\) 辺の単純連結二部グラフの数え上げが分かれば，連結とは限らない \(n\) 頂点 \(m\) 辺の単純二部グラフの数え上げは容易です．\(\mathrm{dp1}[n][m]\) で連結な \(n\) 頂点 \(m\) 辺単純二部グラフの個数，\(\mathrm{dp2}[n][m]\) で連結とは限らない \(n\) 頂点 \(m\) 辺単純二部グラフの個数とします．頂点 \(1\) を含む連結成分の頂点および辺の個数を \(n_1,m_1\) とすれば，\(\mathrm{dp2}[n][m]=\displaystyle \sum_{n_1+n_2=n,m_1+m_2=m} \mathrm{dp1}[n_1][m_1]\times \mathrm{dp2}[n_2][m_2]\times \binom{n-1}{n_1-1}\) が成り立ちます．

実装例 (c++, 170ms)