CF1569F Palindromic Hamiltonian Path

给定一个简单无向图，有 $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$），表示图中的一条边。图中没有重边和自环。

输出一个整数，表示好字符串的数量。

由 ChatGPT 4.1 翻译