|
Гирлянда
(Время: 1 сек. Память: 16 Мб Сложность: 50%)
Приближается Новый Год, и в магазинах начинают появляться различные елочные украшения. На прилавках можно увидеть различные шарики, шишечки, звездочки, но все-таки самым красивым украшением является гирлянда из разноцветных лампочек. Одна из фирм, занимающихся изготовлением елочных украшений, решила в этом году изготавливать гирлянды на заказ.
Гирлянды, изготавливаемые этой фирмы, состоят из лампочек различных цветов, соединенных проводами. Всего в гирлянде n лампочек, каждая из которых покрашена в один из k цветов, и m проводов (каждый провод соединяет ровно две лампочки). Далее мы будем считать, что лампочки пронумерованы натуральными числами от 1 до n.
К сожалению, не каждый дизайн гирлянды соответствует эстетическим взглядам заказчиков. Во-первых, лампочки, соединенные одним проводом должны быть разного цвета, во-вторых, сама конфигурация гирлянды (то есть то, какие лампочки и как соединены проводами) не может быть любой.
Один из отделов фирмы уже провел исследование и нашел наиболее «удачную» конфигурацию. Ваша же задача состоит в том, чтобы найти число способов раскрасить лампочки, чтобы получившаяся гирлянда удовлетворяла эстетическим взглядам заказчиков.
Входные данные
Первая строка входного файла INPUT.TXT содержит три целых числа: n, k, m (1 ≤ n, k ≤ 8, 0 ≤ m ≤ 10). Последующие m строк описывают провода. Описание каждого провода состоит из двух чисел u и v (1 ≤ u, v ≤ n, u ≠ v) – номеров лампочек, соединенных этим проводом.
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2 2 1
1 2 | 2 |
| 2 | 4 4 0 | 256 |
| 3 | 4 4 6
1 2
1 3
1 4
2 3
2 4
3 4 | 24 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
