题目描述

$N$ 頂点 $M$ 辺の単純無向グラフがあります。頂点には $1$ から $N$ までの、辺には $1$ から $M$ までの番号がついています。
辺 $i$ は頂点 $A_i$ と頂点 $B_i$ を結んでいます。
このグラフの各頂点を赤、緑、青の $3$ 色のいずれかで塗る方法であって、以下の条件を満たすものの数を求めてください。

• 辺で直接結ばれている $2$ 頂点は必ず異なる色で塗られている

なお、使われない色があっても構いません。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを出力せよ。

题目大意

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

translated by

3 3
1 2
2 3
3 1

6

3 0

27

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

0

20 0

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 で表すと、以下の $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

Sample Explanation 2

辺がないため、各頂点の色を自由に決めることができます。

Sample Explanation 3

条件を満たす塗り方が存在しない場合もあります。

Sample Explanation 4

答えは $32$ ビット符号付き整数型に収まらないことがあります。