Циклічний транзит#4409
Люк обожнює кататися на громадському транспорті в різних містах, які він відвідує, просто заради задоволення. Він намагається знайти унікальні способи подорожувати по колу: починаючи з однієї станції, подорожуючи через транспортні сполучення до принаймні однієї іншої станції, і повертаючись до початкової станції. Він знаходить багато циклів і хоче дізнатися, скільки їх є в різних транспортних системах. Можливо, їх так багато, що він ніколи не встигне спробувати всі, але йому приносить радість саме їх існування.
Його особливо цікавить підрахунок простих циклів. Простий цикл — це послідовність унікальних транспортних станцій t_1, t_2, \ldots, t_j, де існує спосіб безпосередньо з'єднати t_i з t_{i+1} для 1 \le i < j і також з t_j до t_1. Звісно, ми можемо записати простий цикл, починаючи з будь-якої станції в циклі, тому ми вважаємо будь-який циклічний зсув такої послідовності тим самим простим циклом. Однак два простих цикли, які відвідують той самий набір транспортних станцій у різному порядку, вважаються різними.
Допоможіть Люку, написавши програму для підрахунку кількості унікальних простих циклів у кожній транспортній системі. Наступні рисунки ілюструють транспортні станції (пронумеровані овали) та односторонні сполучення (стрілки) з прикладу вхідних даних.
Вхідні дані містять опис однієї транспортної системи. Опис починається з рядка, що містить ціле число (3 \le m \le 9), яке вказує кількість транспортних станцій у системі. Станції пронумеровані від до m-1. Наступний рядок містить ціле число (1 \le n \le m(m-1)), яке вказує кількість сполучень, що слідують, по одному сполученню на рядок. Кожне сполучення — це пара цілих чисел (0 \le s < m, 0 \le t < m, s \ne t), що вказує на одностороннє сполучення від станції до станції .
Виведіть кількість унікальних простих циклів у транспортній системі.
Приклад 1