Laiko ribojimas: 1s

Atminties ribojimas: 16MB

Duomenų failas: grafas_montekristas.in

Rezultatų failas: grafas_montekristas.out

Jei norite pateikti savo sprendimą - prisijunkite.

Grafas Montekristas

"Kada jau baigsim eit tuos grafus?" - Lironas.

Lironas dovanų gavo... grafą! Kokia neapgalvota dovana - juk vaikinas nėra didelis grafų mėgėjas. "Atkeršysiu tiems grafams!" - pagalvojo Lironas ir pradėjo grafo naikinimo procedūrą. Procedūra vyksta taip: iš pradžių Lironas ant lapo surašo visas grafo briaunas kažkokia tvarka. Po to jis trina tas briaunas iš grafo vieną po kitos taip, kaip užsirašė. Turbūt akivaizdu, kad po kažkiek trynimo operacijų grafas taps nebejungus. Lironui staiga pasidarė įdomu - kiek gi briaunų reikės ištrinti kol grafas pirmą kartą taps nejungus? Padėkite jam tai nustatyti!

Pradiniai duomenys

Pirmoje eilutėje pateikti du sveikieji skaičiai n ir m - grafo viršūnių ir briaunų skaičius (1\\leqn,m\\leq2\\cdotp10^5).

Toliau seka m eilučių. i-ojoje iš jų pateikti du skaičiai u_i ir v_i, nusakantys i-ąją grafo briauną (1\\lequ_i,v_i\\leqn,u_i\\neqv_i).

Lironas grafo briaunas trins būtent tokia tvarka, kuria jos pateiktos šiose m eilučių. Galite tarti, kad kiekviena briauna įvestyje pasirodys ne daugiau kaip vieną kartą.

Rezultatai

Jūsų programa turi išvesti vieną sveikąjį skaičių - po kiek ėjimų grafas pirmą kartą taps nejungus.

Pavyzdžiai

Pradiniai duomenys Rezultatai
5 8
1 2
2 3
1 4
4 2
3 4
5 3
1 5
1 3
4