W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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.
Napisz program, który:
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.
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ć.
Dla danych wejściowych:
2 1 2 1 3 2 3
poprawną odpowiedzią jest:
2