W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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ę .
Napisz program, który:
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 .
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.
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.