D - RGB Coloring 2 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 400 点

問題文

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

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

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

制約

  • 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{15pt} \vdots
A_M B_M

出力

答えを出力せよ。

入力例 1

3 3
1 2
2 3
3 1

出力例 1

6

頂点 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 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 ビット符号付き整数型に収まらないことがあります。

Score : 400 points

Problem Statement

We have a simple undirected graph with N vertices and M edges. The vertices are numbered 1 through N, and the edges are numbered 1 through M.
Edge i connects Vertex A_i and Vertex B_i.
Find the number of ways to paint each vertex in this graph red, green, or blue so that the following condition is satisfied:

  • two vertices directly connected by an edge are always painted in different colors.

Here, it is not mandatory to use all the colors.

Constraints

  • 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
  • The given graph is simple (that is, has no multi-edges and no self-loops).

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

3 3
1 2
2 3
3 1

Sample Output 1

6

Let c_1, c_2, c_3 be the colors of Vertices 1, 2, 3 and R, G, B denote red, green, blue, respectively. There are six ways to satisfy the condition:

  • 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 Input 2

3 0

Sample Output 2

27

Since the graph has no edge, we can freely choose the colors of the vertices.

Sample Input 3

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

Sample Output 3

0

There may be no way to satisfy the condition.

Sample Input 4

20 0

Sample Output 4

3486784401

The answer may not fit into the 32-bit signed integer type.