RGB 三色图着色

题目描述

有一个 $N$ 个顶点、$M$ 条边的简单无向图。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。

边 $i$ 连接顶点 $A_i$ 和顶点 $B_i$。

求用红、绿、蓝这 $3$ 种颜色给这个图的所有顶点染色的方法中，满足以下条件的染色方法数：

• 被边直接连接的两个顶点必须染不同的颜色

另外，允许有颜色不被使用。

输入格式

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

$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$ 位有符号整数类型的表示范围。

数据范围

• $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$
• 给定的图是简单的（不含多重边和自环）