题目描述

$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$ つ存在することが示せます。

输入格式

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

$N$ $M$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$

输出格式

答えを出力せよ。

题目大意

给你一个简单连接的无向图，它有 $N$ 个顶点和 $M$ 条边。(如果一个图没有多条边，也没有自循环，那么这个图就是简单的）。 对于 $i = 1, 2, \ldots, M$，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。

如果同时满足以下两个条件，则称序列 $(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_1,s_2,\ldots ,s_N$ 是由 $0$ 和 $1$ 组成的长度为 $N$ 的字符串。如果满足以下条件，则称路径 $A = (A_1, A_2, \ldots, A_k)$ 为关于 $S$ 的好路径：

• 对于所有 $i = 1, 2, \ldots, N$，成立：
  • 若 $s_i = 0$，则$A$有偶数个 $i$。
  • 若 $s_i = 1$，则$A$有奇数个 $i$。

可能的 $S$ 有 $2^N$ 个（换句话说，由 $0$ 和 $1$ 组成的长度为 $N$ 的字符串有 $2^N$ 个）。求所有这些 $S$ 中"关于 $S$ 的最短好路径的长度"之和。

在这个问题的约束条件下，可以证明对于任何由 $0$ 和 $1$ 组成的长度为 $N$ 的字符串 $S$，至少有一条关于 $S$ 的好路径。

3 2
1 2
2 3

14

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

108

提示

制約

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

Sample Explanation 1

- $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 $ です。