Республиканская олимпиада по информатике 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

Замечание