В этой задаче на проверку необходимо сдать текстовый файл с ответом. Входные данные вы можете скачать, нажав на кнопку с изображением стрелки справа-сверху рядом с кнопкой «Объявления жюри».
Дан неориентированный планарный граф на вершинах и целое положительное число . Назовем раскраску графа красивой, если никакие две соседние его вершины не покрашены в один цвет (для лучшего понимания рекомендуем обратиться к разделу "Примечание"). Найдите количество красивых раскрасок графа в цветов.
В первой строке ввода находится единственное целое число — количество тестовых случаев, которые вам будет необходимо обработать .
Первая строка каждого тестового случая содержит целые числа , и — количество вершин и рёбер графа, а также количество доступных цветов. Ограничения на параметры смотри в разделе «Система оценивания». Обратите внимание, что с ростом значение в тестах убывает.
Следующие строк содержат по два целых числа , задающих рёбра графа.
Для каждого тестового случая выведите единственное число — количество красивых раскрасок графа по модулю .
Оценка за эту задачу — 50 баллов, тестирование проводится оффлайн (баллы за задачу будут известны после окончания тура).
Каждый тестовый случай оценивается независимо. Правильный ответ оценивается в балла. Неправильный ответ оценивается в баллов. Балл за задачу равен сумме баллов по всем тестовым случаям.
Ниже приведены значения в каждом из тестовых случаев.
тест |
тест |
тест |
|||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
1 | 24 | 30 | 4 | 11 | 20 | 25 | 5 | 21 | 11 | 13 | 7 |
2 | 22 | 27 | 4 | 12 | 24 | 30 | 4 | 22 | 12 | 15 | 7 |
3 | 20 | 25 | 5 | 13 | 26 | 32 | 4 | 23 | 13 | 16 | 7 |
4 | 20 | 25 | 6 | 14 | 28 | 35 | 4 | 24 | 14 | 17 | 7 |
5 | 19 | 23 | 5 | 15 | 30 | 37 | 4 | 25 | 15 | 18 | 7 |
6 | 18 | 22 | 7 | 16 | 12 | 15 | 5 | ||||
7 | 18 | 22 | 8 | 17 | 13 | 16 | 5 | ||||
8 | 16 | 20 | 4 | 18 | 14 | 17 | 5 | ||||
9 | 16 | 20 | 5 | 19 | 15 | 18 | 5 | ||||
10 | 15 | 18 | 4 | 20 | 10 | 12 | 7 |
Планарный граф — граф, который можно изобразить на плоскости без пересечений рёбер не по вершинам.
В тесте из условия задан следующий граф: