Решение задачи acmp.ru №874

Приближается Новый Год, и в магазинах начинают появляться различные елочные украшения. На прилавках можно увидеть различные шарики, шишечки, звездочки, но все-таки самым красивым украшением является гирлянда из разноцветных лампочек. Одна из фирм, занимающихся изготовлением елочных украшений, решила в этом году изготавливать гирлянды на заказ.

Гирлянды, изготавливаемые этой фирмы, состоят из лампочек различных цветов, соединенных проводами. Всего в гирлянде 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 выведите ответ на задачу.