← 返回题目列表

AtCoder · abc199_d

D. RGB 着色 2

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

我们有一个简单的无向图 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{15pt} \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 分别表示红色、绿色、蓝色。满足条件的方法有六种:

  • 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- 位有符号整数类型。