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 \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 翻译