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