← 返回题目列表

Codeforces · 1221/G

G. 图表和数字

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

给你一个无向图,其中有 $$$n$$$ 个顶点和 $$$m$$$ 个边。您必须在此图的每个顶点上写下一个数字,每个数字应该是 $$$0$$$ 或 $$$1$$$。之后,在每条边上写入一个数字,该数字等于与该边相关的顶点上的数字之和。

您必须选择要在顶点上写入的数字,以便至少有一条边上写有 $$$0$$$,至少有一条边上写有 $$$1$$$,并且至少有一条边上写有 $$$2$$$。有多少种方法可以做到?如果存在至少一个顶点以这两种方式写有不同的数字,则两种选择数字的方式是不同的。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 40$$$, $$$0 \le m \le \frac{n(n - 1)}{2}$$$) — 分别是顶点数和边数。

接下来是 $$$m$$$ 行,每行包含两个数字 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$) — 第 $$$i$$$ 条边的端点。保证每对顶点最多由一条边连接。

输出

打印一个整数 — 在所有顶点上写数字的方式的数量,以便存在至少一条边上写有 $$$0$$$,至少一条边上写有 $$$1$$$ 和至少一条边上写有 $$$2$$$。

示例

输入 #1

6 5
1 2
2 3
3 4
4 5
5 1

输出 #1

20

输入 #2

4 4
1 2
2 3
3 4
4 1

输出 #2

4

输入 #3

35 29
1 2
2 3
3 1
4 1
4 2
3 4
7 8
8 9
9 10
10 7
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30

输出 #3

34201047040