Красивые раскраски 2047 - 1

Ограничение времени4 секунды
Ограничение памяти256 Мб
Вводстандартный ввод
Выводстандартный вывод

В этой задаче на проверку необходимо сдать исходный код программы.

Дан неориентированный планарный граф на n n вершинах и целое положительное число k k . Назовем раскраску графа красивой, если никакие две соседние его вершины не покрашены в один цвет (для лучшего понимания рекомендуем обратиться к разделу "Примечание"). Найдите количество красивых раскрасок графа в k k цветов.

Формат ввода

В первой строке ввода находится единственное целое число t t  — количество тестовых случаев, которые вам будет необходимо обработать ( 1 t 100 ) (1 \leq t \leq 100) .

Первая строка каждого тестового случая содержит целые числа n n , m m и k k  — количество вершин и рёбер графа, а также количество доступных цветов. Ограничения на параметры смотри в разделе «Система оценивания».

Следующие m m строках содержат по два целых числа u , v u, v , задающих рёбра графа.

Формат вывода

Для каждого тестового случая выведите единственное число — количество красивых раскрасок графа по модулю 1 0 9 + 7 10^9+7 . Гарантируется, что до взятия по модулю ответ не превосходит 50 1 0 6 50\cdot 10^6 .

Система оценивания

Оценка за эту задачу — 50 баллов, тестирование проводится онлайн (после тура баллы за задачу не изменятся).

Каждый тестовый случай оценивается независимо. Правильный ответ оценивается в 2 2 балла. Неправильный ответ оценивается в 0 0 баллов. Балл за задачу равен сумме баллов по всем тестовым случаям.

Ниже приведены значения n , m , k n, m, k в каждом из тестовых случаев.

тест n n m m k k тест n n m m k k тест n n m m k k
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

Примечания

Планарный граф — граф, который можно изобразить на плоскости без пересечений рёбер не по вершинам.

В тесте из условия задан следующий граф:

image