题目描述

我们有一个简单的无向图，其中包含 $N$ 个顶点和 $M$ 条边。顶点编号从 $1$ 到 $N$，边编号从 $1$ 到 $M$。
第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。
找出在该图中给每个顶点涂上红色、绿色或蓝色，使得满足以下条件的涂色方案的数量：

• 直接相连的两个顶点必须涂上不同的颜色。

在这里，并不一定要使用所有的颜色。

约束条件

• $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$
• 给定的图是简单图（即没有重边和自环）。

输入

输入以以下格式从标准输入中给出：

$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $A_3$ $B_3$ $\hspace{13pt} \vdots$ $A_M$ $B_M$

输出

输出答案。

示例输入 1

3 3
1 2
2 3
3 1

示例输出 1

6

设 $c_1, c_2, c_3$ 分别表示顶点 $1, 2, 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 0

示例输出 2

27

因为图中没有边，所以可以随意选择顶点的颜色。

示例输入 3

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

示例输出 3

0

可能无法找到满足条件的方式。

示例输入 4

20 0

示例输出 4

3486784401

答案可能无法用 $32$ 位有符号整数类型表示。