Festyn

Limit pamięci: 64 MB

W Bajtogrodzie trwa festyn charytatywny, a Ty jesteś jedną z kwestujących osób. Ominęło Cię parę atrakcji, w tym bieg z przeszkodami. Bajtazar, miłośnik zagadek logicznych, obiecał przekazać spory datek, jeżeli rozwiążesz jego zagadkę.

Nie znasz dokładnych wyników wyścigu. Bajtazar zdradził Ci jednak część informacji na ich temat, a teraz pyta Cię, ile maksymalnie różnych wyników w wyścigu mogło mieć miejsce. Dwaj uczestnicy mają różne wyniki, jeśli nie przybiegli do mety w tym samym czasie. Dowiedziałeś się, że każdy uczestnik wyścigu uzyskał czas będący całkowitą liczbą sekund. Poznałeś również związki pomiędzy wynikami niektórych par biegaczy. Bajtazar podał Ci część z tych par biegaczy , dla których wynik był dokładnie o jedną sekundę lepszy niż wynik , oraz część z tych par biegaczy , dla których wynik był co najmniej tak samo dobry jak wynik . Napisz program, który pomoże Ci znaleźć rozwiązanie zagadki Bajtazara.

Wejście

Pierwszy wiersz standardowego wejścia zawiera trzy liczby całkowite nieujemne , , (, ), pooddzielane pojedynczymi odstępami, oznaczające odpowiednio: liczbę biegaczy, liczbę poznanych par biegaczy pierwszego typu oraz liczbę poznanych par biegaczy drugiego typu . Biegacze są ponumerowani od 1 do .

W kolejnych wierszach podane są pary biegaczy pierwszego typu, po jednej parze w wierszu - -ty z tych wierszy zawiera dwie liczby i , , oddzielone pojedynczym odstępem, oznaczające, że biegacz miał wynik dokładnie o jedną sekundę lepszy niż biegacz .

W kolejnych wierszach podane są pary biegaczy drugiego typu, po jednej parze w wierszu - -ty z tych wierszy zawiera dwie liczby i , , oddzielone pojedynczym odstępem, oznaczające, że biegacz miał wynik nie gorszy niż biegacz .

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia Twój program powinien wypisać jedną liczbę całkowitą równą maksymalnej liczbie różnych wyników czasowych, jakie mogli osiągnąć biegacze przy założeniu podanych kryteriów.

Jeśli nie istnieje kolejność zawodników spełniająca ograniczenia Bajtazara, wyjście powinno składać się z jednego wiersza zawierającego słowo "NIE" (bez cudzysłowów).

W testach wartych przynajmniej 15% punktów zachodzi dodatkowe ograniczenie .

Przykład

Dla danych wejściowych:

4 2 2
1 2
3 4
1 4
3 1

poprawną odpowiedzią jest:

3

Wyjaśnienie do przykładu: Bieg mógł zakończyć się na dwa sposoby:

1. pierwszy jest biegacz nr 3, na drugim miejscu są ex aequo biegacze nr 1 i 4, a ostatni jest biegacz nr 2;
2. na pierwszym miejscu są ex aequo biegacze nr 1 i 3, a na drugim ex aequo biegacze nr 2 i 4.

Autor zadania: Marian M. Kędzierski.