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