RGB Coloring 2

题目描述

我们有一个由 $N$ 个顶点和 $M$ 条边组成的简单无向图。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。
第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。
求将图中每个顶点涂成红色、绿色或蓝色的方案数，使得满足以下条件：

每条边直接相连的两个顶点必须被涂成不同的颜色。

这里不要求必须使用所有的颜色。

输入格式

输入以标准输入给出，格式如下： $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

3 0

27

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

0

20 0

3486784401

提示

$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$ 所给图是简单图（即不存在多重边和自环）。设 $c_1, c_2, c_3$ 为顶点 $1,2,3$ 的颜色，$R$、$G$、$B$ 分别表示红、绿、蓝。有以下六种满足条件的方式：

$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$
由于图没有边，可以自由选择各顶点的颜色。
可能不存在满足条件的涂色方案。
答案可能无法装入 32 位有符号整数类型。

标签: AtCoder|abc199D

来源

AtCoder|abc199D