| Муниципальный этап ВсОШ по информатике 2026, 9-11 классы, Вологодская область и Краснодарский край |
|---|
| Закончено |
Безумный гений доктор Шпунтик собирает армию боевых роботов-ёжиков из старого металлолома. Перед ним лежит огромная железная конструкция: $$$n$$$ круглых деталей-шестерёнок, которые соединены $$$m$$$ стальными прутьями (каждый прут соединяет ровно две детали). Чтобы активировать одного робота-ёжика, доктору нужно выбрать ровно одну деталь и несколько стальных прутьев, приваренных к этой детали (они станут «иголками»). Для того чтобы робот-ёжик считался правильным и готовым к работе, у него должно быть как минимум три иголки.
Шпунтику не нравится однообразная работа, поэтому каждый его робот должен быть уникальным. Два робота-ёжика считаются различными, если для них выбраны разные детали, или если у них отличается хотя бы одна иголка (выбраны разные наборы прутьев, торчащих из детали). Доктор хочет вычислить, сколько всего различных правильных роботов-ёжиков скрыто в его конструкции. Ёжиков настолько много, что без помощи Шпунтику не справиться. Так как количество роботов может быть очень большим, выведите ответ по модулю $$$10^9 + 7$$$.
Формально: вам дан неориентированный граф. Требуется вычислить количество подграфов вида «ёжик»: в них центральная вершина связана рёбрами с несколькими другими количеством не менее трёх, и других рёбер нет. Обратите внимание: в исходном графе вершины – концы «иголок» «ёжика» могут быть связаны рёбрами, просто при выделении подграфа «ёжик» они в него не включаются. «Ёжики» считаются различными, если есть хотя бы одна вершина, присутствующая в одном из них и отсутствующая в другом. Вам требуется вычислить остаток от деления количества «ёжиков» на число $$$10^9 + 7.$$$
В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$n - 1 \le m \le 3 \cdot 10^5$$$) — количество деталей и прутьев в конструкции соответственно. В следующих $$$m$$$ строках содержатся описания прутьев. Каждая строка содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — начало и конец прута. Гарантируется, что конструкция связная и описания прутьев не повторяются.
Выведите одно целое число — количество различных роботов-ёжиков в заданной конструкции по модулю $$$10^9 + 7$$$ (то есть остаток от деления на $$$10^9 + 7$$$).
Подзадача 1 (до 20 баллов): $$$n, m \le 15$$$
Подзадача 2 (до 24 баллов): $$$n, m \le 2000$$$
Подзадача 3 (до 56 баллов): $$$n, m \le 3 \cdot 10^5$$$
4 31 21 31 4
1
5 41 21 31 41 5
5
Примечание по языку Python. Два числа, записанных через пробел, можно прочитать так:
n, m = map(int, input().split())
| Название |
|---|


