分数: 600 点
问题陈述
AtCoder Town 有 N 交叉路口和 M 道路。
路 i 连接交叉路口 A_i 和 B_i.
高桥市长决定在十字路口安装零个或多个监控摄像头。
每个路口可安装零个或一个监控摄像头。
有多少 2^N 如何安装监控摄像头监控偶数条道路?
这里,路 当满足以下条件时, 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
- (A_i,B_i) \neq (A_j,B_j) if i \neq j.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
输出
打印答案。
示例输入 1
3 2 1 2 2 3
示例输出 1
6
满足条件安装监控摄像头的乡镇套数为: \{ \} , \{ 2 \} , \{ 1,2 \} ,\{1,3\},\{2,3\},\{1,2,3\}.
请注意,允许不安装监控摄像头。
示例输入 2
20 3 5 6 3 4 1 2
示例输出 2
458752
城镇可能无法连接。