eolymp
bolt
Try our new interface for solving problems

Граф

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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

Giriş verilənləri

Первая строка входного файла содержит три целых числа: N, M и K (1N9, 1M100, 1K10). Следующие M строк содержат по два целых числа в пределах от 1 до N — ребра графа. Граф может содержать кратные ребра и петли. Числа в строках разделены пробелом.

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
4 3 2
1 2
2 3
2 4
Çıxış verilənləri #1
8