Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Jei norite pateikti savo sprendimą - prisijunkite.

Kelių konstravimas

Bitlandiją sudaro n miestų ir m kelių, jungiančių miestus. Miestai numeruojami nuo 1 iki n.

Bitlandijos prezidentas pastebėjo, kad kelių sistema seniai neremontuota ir nusprendė sutvarkyti ją - padaryti taip, kad iš bet kurio miesto galima būtų vienu ar daugiau keliais nuvažiuoti į bet kurį kitą miestą. Kad tai padarytų, jis statys naujus kelius.

Aišku, Bitlandijos biudžetas gan ribotas, tad naujų kelių prezidentas statyti norėtų kuo mažiau. Raskite, kiek mažiausiai kelių užteks pastatyti, kad iš bet kurio miesto būtų galima nusigauti į bet kurį kitą.

Pradiniai duomenys

Pirmoje eilutėje pateikti du sveikieji skaičiai n ir m - miesto ir kelių skaičiai (1\\leqn,m\\leq10^5).

Toliau pateikta m eilučių. i-ojoje iš jų yra du tarpu atskirti sveikieji skaičiai u_i ir v_i, reiškiantys, kad tarp miestų u_i ir v_i yra kelias. Yra garantuota, kad nėra kelio, kuris jungia miestą su savimi ir kad nėra pasikartojančių kelių.

Rezultatai

Išveskite vieną skaičių - kiek mažiausiai kelių reikia Bitlandijos prezidentui pastatyti, kad įgyvendintų savo sumanymą.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
7 5
2 1
4 3
5 7
2 3
4 2
 
2
 Galima būtų nutiesti kelius tarp miestų 1 ir 7 bei tarp 5 ir 6. Tuomet iš bet kurio miesto galima patekti į bet kurį kitą. Neįmanoma to pasiekti nutiesiant mažiau nei 2 kelių, tad atsakymas yra 2.