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$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3 2
1 2
2 3

输出 #1

6

输入输出样例 #2

输入 #2

20 3
5 6
3 4
1 2

输出 #2

458752

说明/提示

限制条件

• $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 翻译