Республиканская олимпиада по информатике 2008 год

Задача E. Раскраска графа

Ограничение по времени:

2 секунды

Ограничение по памяти:

64 мегабайт

Рассмотрим неориентированный граф из $N$ вершин и $M$ ребер. Сколькими способами можно раскрасить его вершины в $K$ цветов? Две раскраски считаются одинаковыми, если существует такая перенумерация вершин графа, при которой список ребер остается тем же, и цвета соответствующих вершин совпадут. К примеру, две раскраски на рисунке одинаковы (соответствующая перенумерация: 1->1, 2->2, 3->4, 4->3).

Формат входного файла

Первая строка входного файла содержит три целых числа $N$, $М$ и $K$ (1 <= $K$ <= 10, 1 <= $N$ <= 10, 1 <= $M$ <= 100). Следующие $M$ строк содержат по два целых числа в пределах от 1 до $N$ — ребра графа. Граф может содержать кратные ребра и петли. Каждое ребро встречается не более 7 раз. Числа в строках разделены пробелом.

Формат выходного файла

Выходной файл должен содержать одно целое число — количество различных раскрасок.

Пример:

Вход

4 3 2
1 2
2 3
2 4

Ответ

8

Замечание