AT_abc220_h [ABC220H] Security Camera

AtCoder 町有 $N$ 个交叉路口和 $M$ 条道路。 第 $i$ 条道路连接交叉路口 $A_i$ 和交叉路口 $B_i$。 町长打算在 AtCoder 町的交叉路口上安装 $0$ 个或更多的监控摄像头。 每个交叉路口最多只能安装 $1$ 个监控摄像头，也可以不安装。 监控摄像头的安装方式共有 $2^N$ 种，其中有多少种安装方式能使被监控的道路数为偶数？ 这里，道路 $i$ 被称为“被监控”，当且仅当： > 交叉路口 $A_i$ 和交叉路口 $B_i$ 中，至少有一个安装了监控摄像头。

输入以如下格式从标准输入读入。 > $N$ $M$ > $A_1$ $B_1$ > $A_2$ $B_2$ > $\vdots$ > $A_M$ $B_M$

请输出答案。

## 限制条件 - $2 \leq N \leq 40$ - $1 \leq M \leq \frac{N(N-1)}{2}$ - $1 \leq A_i < B_i \leq N$ - 如果 $i \neq j$，则 $(A_i, B_i) \neq (A_j, B_j)$ - 输入均为整数 ## 样例解释 1 选择安装监控摄像头的交叉路口为 $\{\ \}$、$\{2\}$、$\{1,2\}$、$\{1,3\}$、$\{2,3\}$、$\{1,2,3\}$ 时，均满足条件。注意也可以一个监控摄像头都不安装。 ## 样例解释 2 AtCoder 町不一定是连通的。 由 ChatGPT 4.1 翻译