监控摄像头

题目描述

AtCoder 小镇有 $N$ 个路口和 $M$ 条道路。

第 $i$ 条道路连接路口 $A_i$ 和 $B_i$。

镇长高桥决定在路口安装 0 个或多个监控摄像头。

每个路口可以安装 0 个或 1 个监控摄像头。

在 $2^N$ 种安装方式中，有多少种方式使被监控的道路数量为偶数？

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

• 路口 $A_i$ 和 $B_i$ 中至少有一个安装了监控摄像头。

输入格式

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

$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

小镇不一定是连通的。

数据范围

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