[AdditionalFile5590.zip](file://AdditionalFile5590.zip?type=additional_file)

#5590. 「PA 2017 Final」Niebanalne podróże 2

标签: 传统 | 时间限制: 4000 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2017 Final Niebanalne podróże 2

一年多以前，Bajtazar 成为了在字节国（Bajtocja）旅行的爱好者。这个国家有 $n$ 座城市，由 $m$ 条双向道路连接。Bajtazar 喜欢上了非凡的旅行。在这些旅行中，他从某座城市出发，沿着字节国的道路行进，访问字节国的不同城市，最终返回起始城市。在旅途中，他既不能两次访问任何城市（起始城市除外），也不能两次使用任何一条道路。

字节国的所有道路都是黑色的。Bajtazar 对此并不满意，在下一次非凡的旅行中，他会将走过的每条道路都涂成金丝雀黄。他有多少种不同的方式来给道路上色呢？如果存在一条道路在两种上色方案中颜色不同，我们就认为这两种上色方案是不同的。

输入格式

输入的第一行包含两个整数 $n, m$ $(2 \le n \le 20, 1 \le m \le \frac{n(n-1)}{2})$。

接下来的 $m$ 行每行包含两个自然数 $u_i, v_i$ $(1 \le u_i, v_i \le n, u_i \neq v_i)$，表示城市 $u_i$ 和 $v_i$ 之间有一条双向道路相连。任意两座城市之间最多由一条道路连接。

输出格式

输出一个单独的行，包含一个整数，即可以实现的不同道路上色方案的数量。

样例

输入

4 5
1 2
1 3
1 4
2 3
3 4

输出

3