CF1569F.Palindromic Hamiltonian Path

You are given a simple undirected graph with $n$ vertices, $n$ is even. You are going to write a letter on each vertex. Each letter should be one of the first $k$ letters of the Latin alphabet.

A path in the graph is called Hamiltonian if it visits each vertex exactly once. A string is called palindromic if it reads the same from left to right and from right to left. A path in the graph is called palindromic if the letters on the vertices in it spell a palindromic string without changing the order.

A string of length $n$ is good if:

• each letter is one of the first $k$ lowercase Latin letters;
• if you write the $i$-th letter of the string on the $i$-th vertex of the graph, there will exist a palindromic Hamiltonian path in the graph.

Note that the path doesn't necesserily go through the vertices in order $1, 2, \dots, n$.

Count the number of good strings.

给你一个包含 $n$ 个顶点的简单无向图，其中 $n$ 为偶数。你需要在每个顶点上写一个字母，该字母必须是拉丁字母表前 $k$ 个字母之一。

图中的一条路径称为哈密顿路径，当且仅当它恰好经过每个顶点一次。一个字符串称为回文串，当且仅当它从左到右读与从右到左读完全相同。图中的一条路径称为回文路径，当且仅当按路径中顶点的顺序写出其上的字母所构成的字符串是一个回文串。

一个长度为 $n$ 的字符串称为好字符串，如果满足：

• 字符串中每个字符均为拉丁字母表前 $k$ 个小写字母之一；
• 若将该字符串的第 $i$ 个字符写在图中第 $i$ 个顶点上，则图中存在一条回文哈密顿路径。

注意：该路径不一定按顶点编号顺序 $1, 2, \dots, n$ 经过顶点。

请计算好字符串的个数。

The first line contains three integers $n$, $m$ and $k$ ($2 \le n \le 12$; $n$ is even; $0 \le m \le \frac{n \cdot (n-1)}{2}$; $1 \le k \le 12$) — the number of vertices in the graph, the number of edges in the graph and the number of first letters of the Latin alphabet that can be used.

Each of the next $m$ lines contains two integers $v$ and $u$ ($1 \le v, u \le n$; $v \neq u$) — the edges of the graph. The graph doesn't contain multiple edges and self-loops.

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

接下来的 $m$ 行中，每行包含两个整数 $v$ 和 $u$（$1 \le v, u \le n$；$v \neq u$）—— 表示图中的一条边。该图不含重边和自环。

Print a single integer — number of good strings.

输出一个整数——好字符串的数量。