Turist agentliyi#1777
Anton bir qalaktikalararası səyahət agentliyində işləyir. O, tez-tez bir planetdən digərinə mövcud kosmik gəmi reysləri ilə marşrutlar qurmalı olur. Təəssüf ki, reyslərin sayı məhduddur, ona görə də sərnişinlər çox vaxt aralıq planetlərdə köçürmə etməli olurlar.
Anton müşahidə edib ki, bəzi planetlər köçürmə nöqtəsi kimi digərlərindən daha çox istifadə olunur. O, bunu araşdırmağa qərar alıb: hər bir planetinə görə belə neçə fərqli (B, C) planet cütü mövcuddur ki, -dən -yə gedən hər yol mütləq planetindən keçir.
Antonun bu araşdırmasında ona kömək edin!
Birinci sətirdə iki tam ədəd: və — planetlərin və kosmik gəmi reyslərinin sayı verilir (2 \leq N \leq 20000, 1 \leq M \leq 200000). Sonrakı sətirdən hər biri bir reysi təsvir edir. Hər bir reys iki planeti birləşdirir və hər iki istiqamətdə istifadə oluna bilər. Qarant edilir ki, istənilən planeti digər bir planetdən çatmaq mümkündür.
ədəd tam ədəd çap edin — hər bir planetinə görə elə fərqli planet cütlərinin sayını çap edin ki, birindən digərinə aparan istənilən marşrut mütləq planetindən keçsin.
Nümunə 1