Московская олимпиада школьников 10-11 2025
6 апр 2025, 11:51:53
старт:
6 апр 2025, 10:30:22
финиш:
6 апр 2025, 14:30:22
до финиша:
02:38:27
начало:
6 апр 2025, 10:33:22
конец:
6 апр 2025, 11:00:00
длительность:
04:00:00
...

###### Оценка посылки и тестов

Вердикт ОК как при онлайн проверке теста, так и при оффлайн означает только, что формат выходных данных верный. При этом за тест может быть выставлено и 0 баллов. При онлайн проверке вы видите правильный общий балл. В зачет пойдет последний из них. При оффлаайн проверке будет проверена последняя посылка.

###### Зачет решений

Обратите внимание, что в зачет пойдет результат ПОСЛЕДНЕЙ посылки по любой задаче, даже с онлайн-проверкой. Будьте внимательны, особенно в конце тура.

# D2. Красивые раскраски 2047 - 2

##

В этой задаче на проверку необходимо сдать текстовый файл с ответом. Входные данные вы можете скачать, нажав на кнопку с изображением стрелки справа-сверху рядом с кнопкой «Объявления жюри».

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

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

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

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

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

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

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

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

Оценка за эту задачу — 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 | 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 |  |  |  |

## Примечания

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

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

Набрать здесь Отправить файл
1

    ​

Выбрать Файл не выбран
осталось 100 попыток
Посылок нет