分数: 500 点
问题陈述
给你一个简单的连通无向图 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。 一条路 A = (A_1, A_2, \ldots, A_k) 据说是 好路 关于 S 如果满足以下条件:
- 对于所有人 i = 1, 2, \ldots, N,认为:
- if s_i = 0,那么 A 有偶数个 i的。
- if s_i = 1,那么 A 有奇数个 i的。
有 2^N 可能 S (换句话说,有 2^N 长度的字符串 N 组成 0 和 1)。 求“最短好路径的长度”之和 S“超过所有这些 S.
在本问题的约束下,可以证明,对于任意字符串 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,空序列 () 是最短的好路径 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.
示例输入 2
5 5 4 2 2 3 1 3 2 1 1 5
示例输出 2
108