Маршруты почтальона Нарына


Отправить решение Решать в редакторе

Сложность: 95%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Почтальон из Нарына развозит письма по n сёлам. Между сёлами проложены m дорог с односторонним движением, дорога i ведёт из села a[i] в село b[i] (бывают кольцевые дороги, ведущие из села в него же, и несколько дорог между одной парой сёл).

Маршрутом почтальона назовём последовательность всех дорог, в которой каждая дорога встречается ровно один раз, первая дорога — это дорога номер 1, каждая следующая дорога начинается в селе, где закончилась предыдущая, а последняя дорога заканчивается там, где начинается первая. Два маршрута различаются, если различаются последовательности номеров дорог.

Рисунок

Найдите количество маршрутов по модулю 10⁹ + 7.

Входные данные

В первой строке — два целых числа n и m (1 ≤ n ≤ 300, 1 ≤ m ≤ 10⁵). В каждой из следующих m строк — два целых числа a[i] и b[i] (1 ≤ a[i], b[i] ≤ n).

Выходные данные

Выведите количество маршрутов по модулю 10⁹ + 7.

Пример 1

Вход:

3 5
1 2
2 1
1 3
3 1
1 1

Выход:

2

Пояснение

Дороги примера: 1: 1→2, 2: 2→1, 3: 1→3, 4: 3→1, 5: 1→1. Из села 1 выходят три дороги, после каждого возвращения в село 1 почтальон выбирает одну из ещё не пройденных. Маршрут начинается с дороги 1 (и дороги 2), а дальше дороги 3–4 и 5 можно пройти в любом из двух порядков: получается 2 маршрута.

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

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов m ≤ 10.

Подсказка

Теорема BEST (де Брёйн, ван Аарденне-Эренфест, Смит, Татт): число эйлеровых циклов ориентированного графа равно t(w) · Π (deg(v) − 1)!, где t(w) — число остовных деревьев, ориентированных к любой фиксированной вершине w.


Комментарии

Еще нет ни одного комментария.