H - 安保摄像头

分数：600点

问题描述

AtCoder Town有$N$个交叉口和$M$条道路。 第$i$条道路连接交叉口 $A_i$ 和 $B_i$。

長塚市的市长决定在交叉口上安装一个或多个监控摄像头。 每个交叉口可以安装零个或一个摄像头。

有多少种方式可以安装监控摄像头，使得监控到的道路数量是偶数？

这里，当满足以下条件时，道路 $i$ 被监控到：

安装了一个或多个摄像头在交叉口 $A_i$ 和/或 $B_i$ 上。

约束条件

• $2 \leq N \leq 40$
• $1 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq A_i \lt B_i \leq N$
• 当 $i \neq j$ 时，$(A_i,B_i) \neq (A_j,B_j)$
• 输入值均为整数

输入

输入以以下格式从标准输入给出：

$N$ $M$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_M$ $B_M$

输出

输出答案。

样例输入

3 2
1 2
2 3

样例输出

6

满足条件时可以安装的交叉口集合有：$\{ \} , \{ 2 \} , \{ 1,2 \} ,\{1,3\},\{2,3\},\{1,2,3\}$。 注意，不安装摄像头也是允许的。

样例输入

20 3
5 6
3 4
1 2

样例输出

458752

可能存在不连接的交叉口。