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