English
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/
Zadanie Dwa przyjęcia (dwa)
Dwa przyjęcia
Limit pamięci: 32 MB
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 
zna osobę 
,
to osoba 
zna osobę 
.
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 
(
) - jest to liczba mieszkańców Bajtocji.
Mieszkańcy są ponumerowani od 
do 
.
W kolejnych 
wierszach znajdują się opisy znajomości kolejnych osób.
Na początku 
-szego wiersza występuje
liczba całkowita 
(
) - liczba znajomych
-tego mieszkańca.
Dalej w tym samym wierszu zapisanych jest 
parami różnych
numerów znajomych mieszkańca 
. Zakładamy, że żaden
mieszkaniec nie jest swoim własnym znajomym,
a zatem znajomości wypisane są dwukrotnie:
jeśli 
i 
się znają, to 
występuje na liście
znajomych 
oraz 
na liście znajomych 
.
Wyjście
W pierwszym wierszu standardowego wejścia Twój program powinien
wypisać jedną liczbę całkowitą 
- liczbę osób, które mają przyjść
na pierwsze z przyjęć.
W drugim wierszu należy wymienić 
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
Dla danych wejściowych:
5 3 2 3 4 2 1 3 4 2 1 4 5 2 1 3 1 3
poprawną odpowiedzią jest:
3 1 2 3
W powyższym przykładzie wszystkie osoby będą miały na przyjęciu
parzystą liczbę znajomych.
Autor zadania: Wojciech Guzicki.