题面翻译

给定一个 $N$ 个点 $M$ 条边的简单无向图，要求给每个点染色，共有三种颜色，问最终满足对于任意一条边，其两端节点颜色不同的染色方案数。

translated by

题目描述

有一个简单的无向图，它有 N 个顶点和 M 条边。 顶点的编号从 1 到 N，边的编号从 1 到 M。

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

在满足以下条件的情况下，求该图的每个顶点涂上红、绿、蓝三种颜色中的一种颜色的方法数。

• 由一条边直接连接的 2 个顶点总是涂上不同的颜色。

请注意，可能有一些颜色没有使用。

输入格式

$N$ $M$

$A_1$ $B_1$

$A_2$ $B_2$

$A_3$ $B_3$

$\hspace{15pt}\ \vdots$

$A_M$ $B_M$

输出格式

输出答案。

样例 #1

样例输入 #1

3 3

1 2

2 3

3 1

样例输出 #1

6

样例 #2

样例输入 #2

3 0

样例输出 #2

27

样例 #3

样例输入 #3

4 6

1 2

2 3

3 4

2 4

1 3

1 4

样例输出 #3

0

样例 #4

样例输入 #4

20 0

样例输出 #4

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$

• 给定图形很简单（不包含多条边或自循环）。

Sample Explanation 1

如果顶点 1、2 和 3 的颜色分别用 c_1、c_2 和 c_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

Sample Explanation 2

由于没有边，每个顶点的颜色可以自由确定。

Sample Explanation 3

在某些情况下，可能不存在符合要求的喷涂方法。

Sample Explanation 4

答案可能不适合 32 位有符号整数类型。