分数: 300 点
问题陈述
给你一个无向无权图 N 顶点和 M 既不包含自循环也不包含双边的边。
这里,一个 自循环 是一条边,其中 a_i = b_i (1≤i≤M),和 双边缘 是两条边,其中 (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M).
从顶点开始有多少条不同的路径 1 并访问所有顶点一次?
此处,路径的端点被视为已访问。
例如,我们假设给出了图 1 所示的以下无向图。
图 1:无向图示例
图 2 中所示的以下路径满足条件。
图2:满足条件的路径示例
但是,图 3 中所示的以下路径不满足条件,因为它没有访问所有顶点。
图3:不满足条件的路径示例
下面的路径都不是图4所示的,因为它不是从顶点开始 1.
图4:不满足条件的路径的另一个示例
约束
- 2≦N≦8
- 0≦M≦N(N-1)/2
- 1≦a_i<b_i≦N
- 给定的图既不包含自环也不包含双边。
输入
输入由标准输入按以下格式给出:
N M a_1 b_1 a_2 b_2 : a_M b_M
输出
打印从顶点开始的不同路径的数量 1 并访问所有顶点一次。
示例输入 1
3 3 1 2 1 3 2 3
示例输出 1
2
给定的图形如下图所示:
以下两条路径满足条件:
示例输入 2
7 7 1 3 2 7 3 4 4 5 4 6 5 6 6 7
示例输出 2
1
该测试用例与问题陈述中描述的测试用例相同。