Šeštadieninė informatikos olimpiadininkų mokykla

"Tu iš kaimo!", "Pats tu iš kaimo!" – ginčijasi du kaimiečiai. Iš tiesų, kaip žinoti? Remdamiesi intuicija, kaimiškumą vertinsime pagal atstumą tarp tolimiausių gyvenvietės pažįstamų – kuo šis skaičius mažesnis, tuo didesnis gyvenvietės kaimiškumas. Atstumas tarp dviejų žmonių laikomas lygiu nuliui, jei jie pažįstami tiesiogiai; vienetui, jei jie nepažįstami tiesiogiai, tačiau turi vieną bendrą pažįstamą; dviems – jei kurie nors jų draugai yra pažįstami tiesiogiai, ir t.t.

Parašykite programą, kuri pagal žinomas tiesiogines gyventojų pažintis, apskaičiuotų aprašytąjį gyvenvietės kaimiškumo matą.

Pradiniai duomenys

Pirmoje pradinių duomenų eilutėje įrašytas gyventojų skaičius n (). Gyventojai yra numeruojami nuo 1 iki n. Antroje eilutėje įrašytas pažįstamų gyventojų porų skaičius m. Tolesnėse m eilučių pateikiamos tiesiogiai pažįstamų gyventojų poros.

Pradiniai duomenys bus tokie, kad visi gyventojai bus tiesiogiai ar netiesiogiai pažįstami tarpusavyje.

Rezultatai

Pirmoje ir vienintelėje rezultatų eilutėje turi būti išspausdintas vienintelis skaičius – kaimiškumo matas.

Pavyzdžiai

5
4
1 2
2 3
3 4
4 5

3

5
5
1 2
2 3
3 4
4 5
5 1

1