题目描述

给定一个 $n$ 个顶点 $m$ 条边的无向图, 求其哈密顿路径条数。

本题中, 一条哈密顿路径定义为: 一个 $1$ 到 $n$ 的排列 $p_{1}, p_{2}, \cdots, p_{n}$ 满足, 对于任意 $i(1 \leq i \leq n-1)$ , 无向边 $\left(p_{i}, p_{i+1}\right)$ 存在。

输入格式

第一行两个正整数 $n,m$。

接下来 $m$ 行，每行两个正整数 $u,v$，表示图中的一条无向边 $(u,v)$。

输出格式

一行一个整数，表示图中哈密顿路径条数。由于结果可能过大，你只需要输出答案除以 $2$ 的余数即可。

3 1
1 2

0

样例 1 解释

图不连通，故不存在哈密顿路径，所以哈密顿路径有 $0$ 条，$0$ 除以 $2$ 余数为 $0$。

6 8
2 1
3 4
4 2
6 5
2 5
5 6
1 6
6 2

0

数据规模与约定

对于所有数据, 有 $1 \leq n \leq 30,1 \leq m \leq 300,1 \leq u, v \leq n$ 。

• 子任务 1 (11 分): $n \leq 5$
• 子任务 2 (45 分): $n \leq 17$
• 子任务 3 (14 分): $n \leq 24$
• 子任务 4 (30 分): 无特殊限制

本题启用捆绑测试。