D - RGB Coloring 2

得分：400 分

题目描述

给定一个由 $N$ 个顶点和 $M$ 条边构成的简单无向图。顶点编号为 1 到 $N$，边编号为 1 到 $M$。
第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。
找出满足以下条件的在图中对每个顶点上色的方法的数量：

• 由一条边直接连接的两个顶点必须上不同的颜色。

需要注意一点，不一定要使用全部的颜色。

约束条件

• $1 \le N \le 20$
• $0 \le M \le \frac{N(N - 1)}{2}$
• $1 \le A_i \le N$
• $1 \le B_i \le N$
• 给定的图为简单图（无重边和自环）。

输入

输入以以下格式从标准输入中给出：

$N$ $M$

$A_1$ $B_1$

$A_2$ $B_2$

$A_3$ $B_3$

$\hspace{15pt} \vdots$

$A_M$ $B_M$

输出

打印结果。

3 3
1 2
2 3
3 1

6

设顶点 1, 2, 3 的颜色分别为 $c_1, c_2, c_3$，红色、绿色、蓝色分别用 R, G, B 表示。满足条件的方法有 6 种：

• $c_1c_2c_3 = $ RGB
• $c_1c_2c_3 = $ RBG
• $c_1c_2c_3 = $ GRB
• $c_1c_2c_3 = $ GBR
• $c_1c_2c_3 = $ BRG
• $c_1c_2c_3 = $ BGR

3 0

27

由于图中没有边，我们可以自由选择顶点的颜色。

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

0

有可能没有满足条件的方法。

20 0

3486784401

结果可能无法用 32 位有符号整数类型表示。