次の条件を満たす頂点の部分集合 \(S\) を，よい集合と呼ぶことにします．

• \(|S| \geq 2\)
• \(S\) による誘導部分グラフは，連結な二部グラフである．

連結な単純グラフであって，よい集合に分割できないものを数えることにします． なお，元の問題の答えを求めるためには，\(N\) 頂点の連結なグラフの個数を数える必要があります． これは自明ではありませんが，有名問題なので説明は割愛します．（FPS log の練習問題です．）

そのようなグラフ \(G\) は，以下のように特徴づけられます．

• \(G\) の二重頂点連結成分はすべて，頂点数が奇数の完全グラフである．

まず，十分性は簡単に示せます．

よい集合を任意にとり，\(G\) から取り除くことを考えます． その結果，いくつかの連結成分が残りますが，そのうちの少なくとも \(1\) つが上記の条件を満たすことが確認できます． これで十分性は示せました．

次に必要性を示します．上記の条件を満たさないグラフ \(G\) に対して，よい集合の分割を与えられればよいです．

適当な根をとり，\(G\) の DFS 木を作ります． そして，以下の操作を繰り返してみます．

• 子が \(1\) つ以上存在し，かつそれらがすべて葉であるような頂点 \(v\) をとる．\(v\) とその子たちはよい集合を成すので，これを分割としてとり，グラフから消す．

この結果残る頂点は \(0\) 個か \(1\) 個です． この一連の操作を，アルゴリズムXと呼ぶことにします．

\(G\) が複数の二重頂点連結成分をもつケースは，アルゴリズムXを用いることで，\(G\) 全体が二重頂点連結である場合に帰着できます． 具体的には，まず \(G\) の中で，「頂点数が奇数の完全グラフ」でない二重頂点連結成分をとり，これを一つの頂点に縮約します． その後，縮約した頂点を根としてアルゴリズムXを実行します． この結果根が孤立点として残る場合は簡単で，根を元の二重頂点連結成分に戻し，それを分割すればよいです． そうでない場合，つまり根にいくつかの頂点がつながっている場合もほぼ同様です．根につながっている頂点は，いずれも縮約前のグラフにおいて，根となる二重頂点連結成分のうち，ちょうど一つの頂点とのみ結ばれています． よって，根となる二重頂点連結成分の分割を考え，それに葉を足すような形で，縮約前のグラフの正しい分割を得ることができます．

\(G\) 全体が二重頂点連結である場合を考えます． まず，\(G\) が頂点数偶数の完全グラフである場合は自明です． そうでない時を考えます．

頂点のペア \(x,y\) であって，以下の条件を満たすものを考えます．

• 辺 \((x,y)\) が存在する．
• 頂点 \(x,y\) を縮約することを考える． ただし，縮約後の頂点 \(z\) とその他の頂点 \(v\) の間に辺が存在する条件は，「辺 \((x,v),(y,v)\) のうちちょうど \(1\) つが存在」とする．
• \(x,y\) を縮約した後のグラフは連結である．

このような \(x,y\) が取れたとすると，\(x,y\) を縮約して \(z\) とし，\(z\) を根としてアルゴリズムXを実行すると，正しい分割が得られます．

\(G\) が二重頂点連結であり，かつ完全グラフでないとき，必ず上記の条件を満たす \(x,y\) が取れることを示します． まず，\(G\) の頂点 \(a,b,c\) であって，辺 \((a,b),(b,c)\) が存在し，\((a,c)\) が存在しない，というものが取れます．

\(a\) を根として DFS を実行します． この時，\((a,b),(b,c)\) が DFS 木に含まれるようなDFS木をとります． \(G\) が二重頂点連結であることから，\(a\) は子を \(1\) つしかもたない（\(b\) が唯一の子）であることがわかります．

DFS 木において，\(b\) の子が \(c\) だけのケースを考えます． このときは，\((x,y)=(a,b)\) とすると条件を満たすことがわかります．

\(b\) が \(2\) 個以上の子を持つケースを考えます． \(b\) の子を \(u_1,u_2,\cdots\) とおきます． このとき，各 \(u_i\) について，\(u_i\) の部分木の中に，\(a\) と辺でつながっている頂点が存在します．そうでない場合，\(G\) が二重頂点連結であることに反するためです． 各 \(u_i\) について，\(u_i\) の部分木の中にある \(a\) と辺でつながっている頂点のうち，最も根から遠いものを任意に一つ取り，\(v_i\) とします． このとき，\((x,y)=(a,v_1)\) とすると条件を満たします． これは次のように確認できます． まず，\(v_1\) の直接の子と \(a\) は結ばれていないので，\(z\) と結ばれることになります． また，\(z\) と \(v_i\) (\(2 \leq i\)) も結ばれます． あとは残った DFS 木の辺をたどることで，すべての頂点が連結であることが確認できます．

これで，\(G\) によい分割を与えることができました．

以上の特徴づけを元に，数え上げを解きます． まず，上記の性質を満たすグラフを取り，頂点 \(1\) を根とする BFS 木を作ってみます． それぞれの二重頂点連結成分について，根側の \(1\) つの頂点を除いて，のこりの頂点を同じ”グループ”であるとします． このとき，頂点 \(1\) 以外の各頂点は，ちょうど \(1\) つのグループに所属します． また，各グループは偶数個の頂点を含みます．

今，グループ分けを一つ固定したとします． グループの個数（頂点 \(1\) は数えない）が \(C\) だとすると，このグループ分けを達成するグラフの個数は，\(N^{C-1}\) になります．

これは次のようにわかります． まず，各グループの頂点数が \(d_1,d_2,\cdots,d_C\) だとします． また，頂点 \(1\) をグループ \(0\) と考えて，\(d_0=1\) を定義します． 各グループ \(1 \leq i \leq C\) について，それに対応する”親”の頂点を決めることが，グラフの形状を決定することと対応します． 親をグループ \(j\) から選んだとすると，その中で頂点を選ぶ方法は \(d_j\) 通りあります．

つまり，求めたいものは，以下のような値です．

• \(C+1\) 頂点の根付き木を考える．頂点 \(0\) を根とする．
• 各辺 \((i,j)\) (\(j\) が親) について，\(d_j\) の重みをかける．
• ありえる木の重みの総和はいくらか？

ここで一旦，各辺 \((i,j)\) の重みを \(d_i \times d_j\) としてみます． この問題が解ければ，その結果を \(\prod_{1 \leq i \leq C} d_i\) で割れば元の問題が解けます．

重みが \(d_i \times d_j\) の場合，木を根付きで考える必要はなくなります． 結局この問題は，以下のような問題と同じです．

• サイズ \(d_0,d_1,\cdots,d_C\) の連結成分がある．これらの間に辺を足して全域木を作る方法は何通りか？

これは有名な問題で，その答えは \((\prod_{0 \leq i \leq C} d_i) \times N^{C-1}\) であることが知られています． これは，ケイリーの公式 の”double counting法を用いた証明”と同様に示せます．

\((\prod_{0 \leq i \leq C} d_i) \times N^{C-1}\) を \(\prod_{1 \leq i \leq C} d_i\) で割ることで，あり得るグラフの形状が \(N^{C-1}\) 通りであることがわかりました．

次に，ちょうど \(C\) グループにグループ分けする方法を考えます．\(f(x)=\sum_{n=2,4,6,\cdots} x^n/n!\) とおくと，求める値は \((N-1)! [x^{N-1}] f^C(x)/C!\) です． これに \(N^{C-1}\) かけた値を求め，すべての \(C\) について和を取ればよいです．

結局，求めるべき値は \((N-1)!/N [x^{N-1}] exp(N \times f(x))\) となります． これは \(O(N\log N)\) で計算できるため，十分高速です．

解答例(c++)