Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Гирлянда

(Время: 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.TXTOUTPUT.TXT
12 2 1
1 2
2
24 4 0256
34 4 6
1 2
1 3
1 4
2 3
2 4
3 4
24

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru