Polish version    English version  
  Historia OI -> XII OI 2004/2005


 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
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
III Etap
Przepisy
Dla zawodników
Przydatne zasoby
XI OI 2003/2004
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

Zadanie: Dwa przyjęcia


Król Bajtazar postanowił urządzić dwa wielkie przyjęcia, na które chce zaprosić wszystkich mieszkańców Bajtocji, przy czym każdego na dokładnie jedno z tych przyjęć. Król z własnego doświadczenia wie, że osoba dobrze się bawi na przyjęciu, gdy jest na nim parzysta liczba jej znajomych. Zażądał więc od Ciebie, abyś tak podzielił mieszkańców kraju pomiędzy dwa przyjęcia, żeby jak najwięcej osób miało na swoim przyjęciu parzystą liczbę znajomych. Możliwy jest również taki podział, w którym na jedno z przyjęć nikt nie przyjdzie. Relacja znajomości jest symetryczna, tzn. jeśli osoba A zna osobę B, to osoba B zna osobę A.

Zadanie

Napisz program, który:
  • wczyta ze standardowego wejścia liczbę mieszkańców Bajtocji i opis ich znajomości,
  • podzieli mieszkańców pomiędzy dwa przyjęcia tak, aby ilość osób, które mają na swoim przyjęciu parzystą liczbę znajomych, była jak największa,
  • wypisze na standardowe wyjście listę osób, które powinny przyjść na pierwsze przyjęcie.

Wejście

W pierwszym wierszu standardowego wejścia zapisana jest jedna liczba całkowita N ( 1 <= N <= 200) -- jest to liczba mieszkańców Bajtocji. Mieszkańcy są ponumerowani od 1 do N. W kolejnych N wierszach znajdują się opisy znajomości kolejnych osób. Na początku i + 1-szego wiersza występuje liczba całkowita li ( 0 <= li <= N - 1) -- liczba znajomych i-tego mieszkańca. Dalej w tym samym wierszu zapisanych jest li parami różnych numerów znajomych mieszkańca i. Zakładamy, że żaden mieszkaniec nie jest swoim własnym znajomym, a zatem znajomości wypisane są dwukrotnie: jeśli A i B się znają, to B występuje na liście znajomych A oraz A na liście znajomych B.

Wyjście

W pierwszym wierszu standardowego wejścia Twój program powinien wypisać jedną liczbę całkowitą M -- liczbę osób, które mają przyjść na pierwsze z przyjęć. W drugim wierszu należy wymienić M numerów tych właśnie osób. Pozostałe osoby pójdą na drugie przyjęcie.

W tym zadaniu możliwych jest wiele poprawnych wyników -- Twój program powinien wypisać dowolny z nich.

Przykład


W powyższym przykładzie wszystkie osoby będą miały na przyjęciu parzystą liczbę znajomych.





Wersja do druku