Elektriskās shēmas elementi izvietoti uz izolējoša materiāla plates. Elementu savienojumi ir izveidoti taisnu celiņu veidā. Ja diviem celiņiem ir kopīgs punkts, tad šajā punktā ir elektrisks kontakts.
Lai shēmas elementiem pieslēgtu barošanu, jāpanāk, lai barošana būtu pieslēgta visiem celiņiem un tāpēc dažu celiņu galapunkti jāsavieno ar barošanas bloku.
Uzrakstiet programmu, kas nosaka, kāds mazākais celiņu galapunktu skaits jāpieslēdz barošanas blokam, lai visi shēmas elementi saņemtu barošanu!
Teksta faila elshbaro.dat pirmajā rindā dots naturāls skaitlis - shēmas celiņu skaits N (1≤N≤1000). Katrā no nākošajām N faila rindām doti četri veseli skaitļi x1 y 1 x2 y2 , kas apzīmē viena celiņa gala punktu (x 1,y1) un (x2,y2) koordinātas. Visas koordinātas ir veseli nenegatīvi skaitļi, kas nepārsniedz 1000. Starp katriem diviem blakus skaitļiem ievaddatos ir tukšumsibols.
Teksta faila elshbaro.rez vienīgajā rindā jāizvada naturāls skaitlis - mazākais celiņu galapunktu skaits, kas jāsavieno ar barošanas avotu.
| elshbaro.dat | elshbaro.rez |
3 1 2 4 2 1 1 2 3 3 1 3 2 |
1 |
Piezīme: Tā kā visi celiņi ir savā starpā savienoti, barošanas bloku pietiek pieslēgt jebkura viena celiņa galapunktam.