U Polineziji, poznato je, postoji više od tisuću raštrkanih otoka. U davnoj povijesti ljudi su isključivo naseljavali otoke prevaljujući stotine milja na krhkim lađicama boreći se s vjetrom i morskim strujama. Danas, srećom, postoje trajektne i avionske veze. Međutim, zračna i pomorska kompanija su prilično neusklađene pa je moguće da svojim vezama nisu uspjeli povezati sve otoke. Tvoj zadatak je otkriti koliko je trajektnih ili avionskih veza potrebno da se svi otoci povežu.Ulazni podaci
U prvom retku se nalazi prirodan broj N koji predstavlja broj otoka, 2 ≤ N ≤ 1000. U drugom retku se nalazi prirodan broj K koji predstavlja broj avionskih ili trajektnih linija, 2 ≤ K ≤ 1000. U svakom od sljedećih K redaka nalaze se po dva broja P i Z koji označavaju početni i završni otok pojedine linije. I trajekti i avioni prometuju u oba smjera.
Izlazni podaci
Broj novih linija koje je nužno uvesti kako bi svi otoci bili povezani.
Test primjeri
ulaz
8
4
1 2
1 5
3 2
3 7
|
ulaz
5
3
5 1
2 5
4 3
|
izlaz
3
|
izlaz
1
|
Nema komentara:
Objavi komentar