Školsko natjecanje 2012. godine za 1. i 2. razred Srednje Škole - 3. zadatak

Jedna mala država je imala velikih problema sa cestovnim prometom. Naime, sve ceste u državi su bile poprilično stare i u jako lošem stanju. Državna vlast odlučila je uložiti veliku količinu novca u preuređenje cesta. Voditelji projekta zaključili su da će čitav posao napraviti za jedan vikend i zaustaviti promet u cijeloj državi. Planirali su u subotu srušiti sve ceste, a u nedjelju izgraditi nove.

Sve je išlo po planu, dok nije zapuhao jak vjetar i odnio nacrte na kojima su bile ucrtane ceste. Kako se bliži kraj dana, voditelje projekta hvata panika.

Voditeljima je poznato da država ima N gradova i da je pomoću starih cesta bilo moguće doputovati iz bilo kojeg grada u bilo koji drugi grad. Uz to voditelji znaju koliko je cesta do sada izgrađeno.

Pomozite voditeljima izračunati koliko još najmanje cesta moraju izgraditi do kraja dana, tako da bude moguće putovati između bilo koja dva grada.

ULAZNI PODACI

U prvom retku se nalazi prirodan broj N (2 ≤ N ≤ 1000), koji predstavlja broj gradova u državi.

U drugom retku se nalazi prirodan broj K (2 ≤ K ≤ 1000), koji predstavlja broj cesta koje su sagrađene.

U svakom od sljedećih K redaka nalaze se po dva broja xi i yi , (1 ≤ xi , yi ≤ N), koji znače da i-ta sagrađena cesta direktno povezuje gradove xi i yi , s tim da su gradovi numerirani od 1 do N, a sve ceste su dvosmjerne.

IZLAZNI PODACI

U prvom i jedinom retku potrebno je ispisati najmanji broj cesta koje je potrebno sagraditi, tako da bude moguće doputovati iz bilo kojeg grada u bilo koji drugi grad.

PRIMJERI TEST PODATAKA

ulaz

3
3
3 2
2 1
1 3

izlaz

0

ulaz

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

izlaz

1

ulaz

8
6
6 3
2 1
7 4
5 7
4 5
3 4

izlaz

2