AT_abc199_d [ABC199D] 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$

输出格式

请输出答案。

样例 1

输入

3 3
1 2
2 3
3 1

输出

6

样例 2

输入

3 0

输出

27

样例 3

输入

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

输出

0

样例 4

输入

20 0

输出

3486784401

说明/提示

限制条件

• $1 \leq N \leq 20$
• $0 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq A_i \leq N$
• $1 \leq B_i \leq N$
• 给定的图是简单图（不包含重边和自环）

样例解释 1

将顶点 $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

样例解释 2

由于没有边，因此每个顶点的颜色可以自由选择。

样例解释 3

有些情况下不存在满足条件的染色方法。

样例解释 4

答案可能超过 $32$ 位有符号整数的范围。

由 ChatGPT 4.1 翻译