Polish version    English version  
  Historia OI -> XI OI 2003/2004 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
III Etap
Przepisy
Dla zawodnikow
Przydatne zasoby
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
XI Olimpiada Informatyczna 2003/2004

Zadanie: tur

Turniej

Zawody II stopnia  
Plik źródłowy: tur.xxx (xxx=pas,c,cpp)
Limit pamięci: 32 MB

Alternatywne formaty: PostScript

Światowa Federacja Gry X organizuje turniej programów grających w tę grę. Startuje w nim n programów ponumerowanych od 1 do n. Zasady rozgrywania turnieju są następujące: dopóki w turnieju pozostaje więcej niż jeden program, losowane są dwa różne spośród nich, które rozgrywają partię gry X. Przegrany (w grze X nie ma remisów) odpada z turnieju, po czym cała procedura jest powtarzana. Program, który pozostanie w turnieju jako jedyny po rozegraniu wszystkich n-1 gier, zostaje zwycięzcą.

Federacja dysponuje tabelą wyników poprzednich turniejów. Wiadomo, że programy grają deterministycznie (tzn. w powtarzalny sposób) i tak samo jak w poprzednich turniejach. Zatem jeżeli pewne dwa programy już kiedyś ze sobą grały, to na pewno ich kolejna gra zakończy się tak samo. Jeśli jednak dwa programy jeszcze nigdy nie walczyły ze sobą, rezultatu rozgrywki nie da się przewidzieć - oba mają szansę na wygraną. Federacja chciałaby poznać listę wszystkich tych programów, które mają szansę na wygranie turnieju.

Zadanie

Napisz program, który:

  • wczyta ze standardowego wejścia liczbę uczestniczących programów oraz tabelę wyników ich wcześniejszych gier,
  • wyznaczy wszystkie programy, które mają szansę wygrać turniej,
  • wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz wejścia zawiera liczbę całkowitą n, 1 <= n <= 100.000. Kolejnych n wierszy zawiera tabelę wyników wcześniejszych gier: i+1-szy wiersz zawiera liczbę całkowitą  k_i, 0 <= k_i < n, a następnie k_i numerów programów, różnych od i, podanych w kolejności rosnącej - są to numery programów, z którymi program nr  i już kiedyś wygrał. Liczby w wierszach są pooddzielane pojedynczymi odstępami. Liczba wszystkich znanych wyników wcześniejszych gier nie przekracza 1.000.000.

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać liczbę w wszystkich programów, które mają szansę wygrać turniej, a następnie w liczb będących numerami tych programów, podanymi w kolejności rosnącej. Liczby w wierszu powinny być pooddzielane pojedynczymi odstępami.

Przykład

Dla danych wejściowych:


4
2 2 3
0
1 2
1 2

prawidłową odpowiedzią jest:

3 1 3 4



Wersja do druku