İttifaqlar#5221
Triametist Krallığında şəhər və onların bəzilərini birləşdirən yol var. Bir gün, saray sehrbazı D-nin bir təcrübəsi nəticəsində sirli bir hadisə baş verdi: krallıq kainatda bir neçə nüsxəyə, yəni əkslərə bölündü. Hər bir əksdə isə, hər yol ya alfa, ya da omega cadu ilə sehrlənmişdir. Diqqəti çəkən məqam odur ki, yolların sehrlənməsinin bütün mümkün kombinasiyaları məhz bir əksdə mövcuddur.
Bu cadu növlərinin xüsusi bir xassəsi var: , və şəhərləri ticarət ittifaqı təşkil edirlərsə, yalnız və yalnız ilə -ni, ilə -ni, və ilə -nı birləşdirən yolların hamısı eyni cür cadulanıbsa (hamısı ya alfa, ya da omega cadusu ilə), bu baş verir.
Girişin birinci sətrində Triametist Krallığındakı şəhərlərin sayı və yolların sayı verilir. Növbəti sətrin hər birində bir cüt ədəd verilir, bu da bir yolun birləşdirdiyi şəhərləri göstərir. Məhdudiyyətlər: 3 \leq n \leq 20000, 1 \leq m \leq 500000. Heç bir iki şəhər arasında bir yoldan çox yol yoxdur və heç bir yol öz-özünə qayıtmır.
Yeganə real ədəd çıxışa verin — Triametist Krallığının bütün əkslərində yaradılan ticarət ittifaqlarının orta sayını ən yüksək dəqiqliklə göstərin.
Nümunə 1