配点 : $500$ 点

問題文

$N$ 個の頂点と $M$ 本の辺からなる単純（自己ループおよび多重辺を持たない）かつ連結な無向グラフが与えられます。 $i = 1, 2, \ldots, M$ について、$i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結びます。

下記の $2$ つの条件をともに満たす整数列 $(A_1, A_2, \ldots, A_k)$ を長さ $k$ のパスと呼びます。

• すべての $i = 1, 2, \dots, k$ について、$1 \leq A_i \leq N$ 。
• すべての $i = 1, 2, \ldots, k-1$ について、頂点 $A_i$ と頂点 $A_{i+1}$ は辺で直接結ばれている。

空列も長さ $0$ のパスとみなします。

$S = s_1s_2\ldots s_N$ を $0$ と $1$ のみからなる長さ $N$ の文字列とします。 パス $A = (A_1, A_2, \ldots, A_k)$ が下記を満たすとき、パス $A$ を $S$ に関する良いパスと呼びます。

• すべての $i = 1, 2, \ldots, N$ について、次を満たす。- $s_i = 0$ ならば、$A$ に含まれる $i$ の個数は偶数である。
  • $s_i = 1$ ならば、$A$ に含まれる $i$ の個数は奇数である。

$S$ として考えられる文字列（すなわち、$0$ と $1$ のみからなる長さ $N$ の文字列）は $2^N$ 個ありますが、そのすべてにわたる「 $S$ に関する良いパスのうち最短のものの長さ」の総和を出力してください。

この問題の制約下において、$0$ と $1$ からなる長さ $N$ のどのような文字列を $S$ として選んでも、$S$ に関する良いパスが少なくとも $1$ つ存在することが示せます。

制約

• $2 \leq N \leq 17$
• $N-1 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq u_i, v_i \leq N$
• 与えられるグラフは単純かつ連結
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_M$ $v_M$

出力

答えを出力せよ。

3 2
1 2
2 3

14

• $S = 000$ のとき、空列 $()$ は $S$ に関する最短の良いパスであり、その長さは $0$ です。
• $S = 100$ のとき、$(1)$ は $S$ に関する最短の良いパスであり、その長さは $1$ です。
• $S = 010$ のとき、$(2)$ は $S$ に関する最短の良いパスであり、その長さは $1$ です。
• $S = 110$ のとき、$(1, 2)$ は $S$ に関する最短の良いパスであり、その長さは $2$ です。
• $S = 001$ のとき、$(3)$ は $S$ に関する最短の良いパスであり、その長さは $1$ です。
• $S = 101$ のとき、$(1, 2, 3, 2)$ は $S$ に関する最短の良いパスであり、その長さは $4$ です。
• $S = 011$ のとき、$(2, 3)$ は $S$ に関する最短の良いパスであり、その長さは $2$ です。
• $S = 111$ のとき、$(1, 2, 3)$ は $S$ に関する最短の良いパスであり、その長さは $3$ です。

よって、求める答えは $0 + 1 + 1 + 2 + 1 + 4 + 2 + 3 = 14$ です。

5 5
4 2
2 3
1 3
2 1
1 5

108