← 返回题目列表

AtCoder · abc220_h

H. 监控摄像头

中文机器翻译题面 查看原题

分数: 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

城镇可能无法连接。