最短好路径

题目描述

给定一个具有 $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 \le A_i \le N$。
• 对所有 $i = 1, 2, \ldots, k-1$,顶点 $A_i$ 和顶点 $A_{i+1}$ 之间有边直接相连。

空序列视为长度为 $0$ 的路径。

设 $S = s_1s_2\ldots s_N$ 为长度为 $N$、由 $0$ 和 $1$ 组成的字符串。 当路径 $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$ 种(也就是说,长度为 $N$、由 $0$ 和 $1$ 组成的字符串共有 $2^N$ 个)。求所有 $S$ 的「关于 $S$ 的最短好路径的长度」之和。

在本题的数据范围下,可以证明:对任意长度为 $N$、由 $0$ 和 $1$ 组成的字符串 $S$,至少存在一条关于 $S$ 的好路径。

输入格式

输入按以下格式从标准输入给出:

N M
u_1 v_1
u_2 v_2
⋮
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

数据范围

• $2 \le N \le 17$
• $N-1 \le M \le \frac{N(N-1)}{2}$
• $1 \le u_i, v_i \le N$
• 给定的图是简单且连通的。
• 输入中的所有值均为整数。