Sojusz
Limit pamięci: 32 MB
Dawno, dawno temu, w odległej galaktyce istniały dwa państwa, które postanowiły zawrzeć sojusz.
Każde z państw obejmowało pewną liczbę planet.
Niektóre z planet były połączone wygodnymi tunelami nadprzestrzennymi I generacji.
Każdy tunel łączył dwie planety i pozwalał na odbywanie podróży pasażerskich między nimi w krótkim czasie.
Pewnego dnia naukowcy odkryli tunele nadprzestrzenne II generacji, które pozwalały odbywać podróże w jeszcze krótszym czasie.
Ulepszenie tunelu starszego typu do tunelu II generacji kosztowało wszędzie tyle samo.
Politycy obu państw postanowili umocnić sojusz ulepszając do tuneli II generacji niektóre tunele I generacji łączące planety z różnych państw.
Aby żadna planeta nie czuła się skrzywdzona, ustalono, że każda planeta, która już posiadała jakiś tunel I generacji łączący ją z planetą przeciwnego państwa, powinna mieć ulepszony przynajmniej jeden z tych tuneli.
Przystąpiono do realizacji planów, ale wydano zbyt dużo pieniędzy, oba państwa zbankrutowały, sojusz się rozpadł, a w galaktyce zapanował kosmiczny chaos.
Obecnie niektórzy historycy badający tamte wydarzenia uważają, że ulepszono wówczas zbyt wiele tuneli, a całego zamieszania można było uniknąć.
Z chęcią dowiedzieliby się, jaka była minimalna liczba tuneli, które trzeba było unowocześnić, by spełnić ustalenia polityków.
Twoim zadaniem będzie im w tym pomóc.
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia opis sieci tuneli I generacji,
- znajdzie minimalną liczbę tuneli, które należało ulepszyć,
aby spełnić wymagania ustalone przez polityków,
- zapisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu znajdują się dwie liczby całkowite
i , oddzielone pojedynczym odstępem i określające odpowiednio liczby planet
w pierwszym i drugim państwie, .
Przyjmujemy, że planety w pierwszym państwie są ponumerowane liczbami całkowitymi
od 1 do , natomiast w drugim liczbami całkowitymi od do .
Drugi wiersz zawiera jedną liczbę całkowitą , .
Jest to liczba tuneli I generacji.
Następne wierszy zawiera opisy tuneli.
Pojedynczy wiersz opisuje jeden tunel i zawiera parę liczb ,
oddzielonych pojedynczym odstępem, gdzie i są numerami planet połączonych tunelem.
Zakładamy, że żaden tunel nie łączy planety z nią samą
i że żadna para planet nie jest połączona kilkoma tunelami.
Wyjście
W pierwszym i jedynym wierszu wyjścia powinna znaleźć się jedna liczba całkowita,
będąca minimalną liczbą tuneli, które należało ulepszyć.
Przykład
Dla danych wejściowych:
2 1
2
1 3
2 3
poprawną odpowiedzią jest:
2