← 返回题目列表

AtCoder · abc054_c

C. 一笔路径

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

分数: 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

给定的图形如下图所示:

43c0ac53de20d989d100bf60b3cd05fa.png

以下两条路径满足条件:

c4a27b591d364fa479314e3261b85071.png

示例输入 2

7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7

示例输出 2

1

该测试用例与问题陈述中描述的测试用例相同。