Задача: D2. Красивые раскраски 2047

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

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

Первая строка каждого тестового случая содержит целые числа \(n\), \(m\) и \(k\) — количество вершин и рёбер графа, а также количество доступных цветов \((1 \leq n \leq 30, 1 \leq m \leq 40, 1 \leq k \leq 11)\). Обратите внимание, что с ростом \(n\) значение \(k\) в тестах убывает.

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

Для каждого тестового случая выведите единственное число — количество красивых раскрасок графа по модулю \(10^9+7\).

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

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

Ваш ответ: