Задан простой неориентированный граф с $$$n$$$ вершинами, $$$n$$$ четно. Вы планируете написать одну букву на каждой вершине. Каждая буква должна быть одной из первых $$$k$$$ букв латинского алфавита.
Путь в графе называется гамильтоновым, если он посещает каждую вершину ровно один раз. Строка называется палиндромной, если она читается одинаково слева направо и справа налево. Путь в графе называется палиндромным, если при выписывании букв с вершин в порядке пути получается палиндромная строка.
Строка длины $$$n$$$ хорошая, если:
Обратите внимание, что путь не обязан проходить по вершинам в порядке $$$1, 2, \dots, n$$$.
Посчитайте количество хороших строк.
В первой строке записаны три целых числа $$$n$$$, $$$m$$$ and $$$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$$$) — ребра графа. Граф не содержит кратных ребер и петель.
Выведите одно целое число — количество хороших строк.
4 3 3 1 2 2 3 3 4
9
4 6 3 1 2 1 3 1 4 2 3 2 4 3 4
21
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
456165084
