Hide

Problem D
Neðanjarðargöng

Languages en is

Þar sem neðanjarðargöngin milli Veraldar og Háskólatorgs slógu svona í gegn ætlar Háskóli Íslands nú að tengja allar byggingarnar sínar með neðanjarðargöngum. Stundum þarf samt að sinna viðhaldi á slíkum göngum svo velja þarf göngin þannig að hægt sé að komast milli allra bygginga þó svo að lokað sé á ein göng, sama hvaða göng það eru. Það er þegar búið að byrja á þessu verki og nú er verið að skoða hvernig gengur. Getur þú ákvarðað hvað þarf að bæta við mörgum tengingum í viðbót til þess að uppfylla kröfur háskólans?

Inntak

Fyrsta lína inntaksins inniheldur heiltölur $0 \leq n, m \leq 10^5$ þar sem $n$ er fjöldi bygginga og $m$ er fjöldi gangna sem komin eru þegar. Síðan fylgja $m$ línur, hver með tveimur heiltölum $1 \leq a, b \leq n$ sem segir að búið sé að byggja göng frá byggingu númer $a$ til byggingu númer $b$. Hægt er að ferðast eftir göngunum í báðar áttir. Ekki er búið að byggja fleiri en eina göng milli tveggja bygginga og engin göng fara frá byggingu í sjálfa sig.

Úttak

Eina línu með einni heiltölu, fjölda ganga sem þarf að bæta við til að uppfylla kröfur háskólans.

Sample Input 1 Sample Output 1
6 5
1 2
3 2
2 5
4 5
6 5
2
Sample Input 2 Sample Output 2
3 3
1 2
2 3
3 1
0