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