Маршруты почтальона Нарына
Почтальон из Нарына развозит письма по 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.
Комментарии