← 返回题目列表

Codeforces · 1569/F

F. 回文哈密顿路径

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

给你一个简单的无向图,有 $$$n$$$ 个顶点,$$$n$$$ 是偶数。您将在每个顶点上写一个字母。每个字母应该是拉丁字母表中前 $$$k$$$ 字母之一。

如果图中的路径恰好访问每个顶点一次,则该路径称为哈密顿量。如果一个字符串从左到右和从右到左读取相同,则称为回文字符串。如果图中顶点上的字母在不改变顺序的情况下拼成回文字符串,则该路径被称为回文路径。

长度为 $$$n$$$ 的字符串适合以下情况:

- 每个字母都是前 $$$k$$$ 小写拉丁字母之一;
- 如果将字符串的第 $$$i$$$ 个字母写在图的第 $$$i$$$ 个顶点上,则图中将存在一条回文哈密顿路径。

请注意,路径不一定按 $$$1, 2, \dots, n$$$ 的顺序经过顶点。

计算好字符串的数量。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \le n \le 12$$$; $$$n$$$ 是偶数; $$$0 \le m \le \frac{n \cdot (n-1)}{2}$$$; $$$1 \le k \le 12$$$) —图中的顶点、图中的边数以及可以使用的拉丁字母表的第一个字母的数量。

接下来的 $$$m$$$ 行包含两个整数 $$$v$$$ 和 $$$u$$$ ($$$1 \le v, u \le n$$$; $$$v \neq u$$$) - 图形的边缘。该图不包含多条边和自环。

输出

打印一个整数——好字符串的数量。

示例

输入 #1

4 3 3
1 2
2 3
3 4

输出 #1

9

输入 #2

4 6 3
1 2
1 3
1 4
2 3
2 4
3 4

输出 #2

21

输入 #3

12 19 12
1 3
2 6
3 6
3 7
4 8
8 5
8 7
9 4
5 9
10 1
10 4
10 6
9 10
11 1
5 11
7 11
12 2
12 5
12 11

输出 #3

456165084