问题描述

给定一个简单的连通无向图，有 $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_1s_2\ldots s_N$ 是一个长度为 $N$ 的由 $0$ 和 $1$ 组成的字符串。如果对于 $S$，满足以下条件的路径 $A = (A_1, A_2, \ldots, A_k)$ 被称为好路径：

• 对于所有的 $i = 1, 2, \ldots, N$，都满足：
  • 如果 $s_i = 0$，那么 $A$ 中 $i$ 的个数是偶数。
  • 如果 $s_i = 1$，那么 $A$ 中 $i$ 的个数是奇数。

共有 $2^N$ 种可能的 $S$（换句话说，有 $2^N$ 个由 $0$ 和 $1$ 组成、长度为 $N$ 的字符串）。计算所有这些 $S$ 对应的好路径的最短长度之和。

在问题的限制条件下，可以证明，对于任意长度为 $N$ 的由 $0$ 和 $1$ 组成的字符串 $S$，至少存在一条满足条件的好路径。

约束条件

• $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$

输出

输出答案。

示例输入 1

3 2
1 2
2 3

示例输出 1

14

• 对于 $S = 000$，空序列 $()$ 是对应的好路径，其长度为 $0$。
• 对于 $S = 100$，$(1)$ 是对应的好路径，其长度为 $1$。
• 对于 $S = 010$，$(2)$ 是对应的好路径，其长度为 $1$。
• 对于 $S = 110$，$(1, 2)$ 是对应的好路径，其长度为 $2$。
• 对于 $S = 001$，$(3)$ 是对应的好路径，其长度为 $1$。
• 对于 $S = 101$，$(1, 2, 3, 2)$ 是对应的好路径，其长度为 $4$。
• 对于 $S = 011$，$(2, 3)$ 是对应的好路径，其长度为 $2$。
• 对于 $S = 111$，$(1, 2, 3)$ 是对应的好路径，其长度为 $3$。

因此，答案等于 $0 + 1 + 1 + 2 + 1 + 4 + 2 + 3 = 14$。

示例输入 2

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

示例输出 2

108