Loopy tranzit#4409
Luke müxtəlif şəhərlərdə ictimai nəqliyyatda səyahət etməyi sevir və o, dövrə vuraraq səyahət etməyin unikal yollarını tapmağa çalışır. Bu, bir nəqliyyat stansiyasından başlayaraq, ən azı bir başqa stansiyaya nəqliyyat bağlantıları boyunca səyahət edib başladığı stansiyaya qayıtmaq deməkdir. Luke çoxlu dövrələr tapır və müxtəlif nəqliyyat sistemlərində nə qədər dövrə olduğunu bilmək istəyir. Ola bilsin ki, onların hamısını heç vaxt sınamağa vaxtı çatmayacaq, amma onların mövcud olduğunu bilməkdən məmnun olacaq.
O, xüsusilə sadə dövrələr sayını hesablamağa maraqlıdır. Sadə dövrə, t_1, t_2, ..., t_j unikal nəqliyyat stansiyalarının ardıcıllığıdır, burada 1 ≤ i < j üçün t_i-dən t_{i+1}-ə birbaşa əlaqə qurmağın yolu var və həmçinin t_j-dən t_1-ə. Əlbəttə ki, sadə dövrəni dövrədəki istənilən stansiyadan başlayaraq yaza bilərik, buna görə də belə bir ardıcıllığın hər hansı dövri dəyişməsi eyni sadə dövrə hesab olunur. Lakin, eyni dəst nəqliyyat stansiyalarını fərqli ardıcıllıqla ziyarət edən iki sadə dövrə fərqli hesab olunur.
Luke-a hər nəqliyyat sistemində neçə unikal sadə dövrə olduğunu sayan bir proqram yazmaqda kömək edin. Aşağıdakı şəkillər nümunə girişinin nəqliyyat stansiyalarını (nömrələnmiş ovalar) və bir istiqamətli bağlantıları (oxlar) göstərir.
Giriş bir nəqliyyat sisteminin təsvirini ehtiva edir. Təsvir 3 ≤ m ≤ 9 tam ədədini ehtiva edən bir sətirlə başlayır, bu sistemdəki nəqliyyat stansiyalarının sayını göstərir. Stansiyalar 0 ilə m−1 arasında nömrələnir. Növbəti sətir 1 ≤ n ≤ m(m−1) tam ədədini ehtiva edir, bu isə ardınca gələn bağlantıların sayını göstərir, hər sətirdə bir bağlantı. Hər bağlantı s t (0 ≤ s < m, 0 ≤ t < m, s ≠ t) tam ədədlər cütüdür, bu isə stansiya s-dən stansiya t-yə bir istiqamətli bağlantının olduğunu göstərir.
Nəqliyyat sistemindəki unikal sadə dövrələrin sayını çap edin.
Nümunə 1