Ustawiony turniej
Limit pamięci: 32 MB
Turniejem nazwiemy cykl rozgrywek pomiędzy zawodnikami, w którym
po każdym meczu pomiędzy dwoma zawodnikami przegrywający odpada z dalszych rozgrywek, a wygrywający
pozostaje w turnieju (każdy mecz musi zostać rozstrzygnięty, nie ma remisów).
Turniej kończy się, gdy pozostanie w nim dokładnie jeden zawodnik - zwycięzca.
Wyznaczenie harmonogramu spotkań w turnieju należy do Naczelnej Federacji Sportowej (NFS).
Członkowie tej federacji mają prawo wskazać, którzy zawodnicy rozgrywają pierwszy mecz.
Następnie, gdy znany jest już wynik pierwszego spotkania, wskazują, którzy zawodnicy (z pozostałych w turnieju) spotykają się w drugim meczu.
Następnie wyznaczają przeciwników w trzecim meczu, itd.
aż w turnieju pozostanie tylko jeden zawodnik.
Łatwo zauważyć, że o zwycięstwie w turnieju decyduje nie tylko wytrenowanie i umiejętności zawodników, ale również "szczęście" - tzn.
harmonogram rozgrywek.
Wiedzą o tym również członkowie NFS.
Ponadto to wysokie gremium wykorzystało odpowiednio okres treningów, obserwując uważnie
osiągnięcia zawodników i szacując ich szansę w nadchodzącym turnieju.
W chwili obecnej, u progu sezonu, wiadomo już, że wyniki ewentualnych spotkań pomiędzy pewnymi zawodnikami są z góry przesądzone.
Dysponując taką informacją, NFS zastanawia się, czy można ułożyć harmonogram
spotkań w ten sposób, by doprowadzić do wygranej pewnego, wybranego zawodnika , tzn.
tak zaplanować mecze, by spotykał się tylko z takimi przeciwnikami, z którymi
na pewno wygra (to oczywiście sprawi, że wygra cały turniej).
Gdyby się to udało, to powiemy, że turniej jest ustawiony dla zawodnika .
Zadanie
Twoim zadaniem jest napisanie programu, który pozwoli wyznaczyć grupę zawodników (ich liczbę), dla których można ustawić turniej.
Wejście
Program powinien czytać dane ze standardowego wejścia.
W pierwszym wierszu podana jest liczba
(), która oznacza liczbę zawodników biorących udział w turnieju.
Zawodników będziemy oznaczać liczbami .
W następnym wierszu podana jest lista zawodników, którzy na pewno wygrywają w bezpośrednim
spotkaniu z zawodnikiem .
Lista składa się z liczby
(oznaczającej liczbę zawodników "lepszych" od zawodnika )
i następujących po niej numerów zawodników .
Wszystkie te liczby oddzielone są pojedynczymi odstępami.
W kolejnych wierszach podane są analogiczne listy dla zawodników .
Uwaga 1: Fakt, że zawodnik przegrałby z zawodnikiem ,
a z , nie musi oznaczać, że przegrałby z ,
gdyby doszło do bezpośredniego spotkania między nimi.
Uwaga 2: W danych nie ma takich paradoksalnych sytacji, że zawodnik
znajduje się na liście lepszych od zawodnika i jednocześnie zawodnik jest na liście zawodnika .
Wyjście
Program powinien wypisać wynik na standardowe wyjście.
Wynikiem powinna być jedna liczba oznaczająca liczbę zawodników, dla których można "ustawić" turniej.
Przykład
Dla danych wejściowych:
3
2 3 2
1 3
0
poprawną odpowiedzią jest:
1