当前没有测试数据。

F - 最短好路径

给定一个有$N$个顶点和$M$条边的简单连通无向图（简单图没有重边和自环）

对于$i=1,2,\ldots,M$，第$i$条边连接顶点$u_i$和$u_i$。

如果满足以下两个条件，那么序列$(A_1,A_2,\ldots,A_k)$被称为长度为$k$的路径：

• 对于所有的$i=1,2,\ldots,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$成立：
  • 如果$s_i=0$，则$A$中$i$的数目是偶数。
  • 如果$s_i=1$，则$A$中$i$的数目时奇数。

共有$2^N$种可能的$S$（换句话说，存在$2^N$个长度为$N$且由$0$和$1$组成的字符串）。求出所有这些$S$相对于$S$的最短好路径长度的和。

在问题的约束下，可以证明，对于长度为$N$且由$0$和$1$组成的字符串$S$，至少存在一条相对于$S$的好路径。

约束条件

• $2\leq N\leq17$
• $N-1\leq M\leq \frac{N(N-1)}{2}$

输入 标准输入包含如下格式的数据 $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$，偶数个$i$的空序列$()$是相对于$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