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.
W remizie strażackiej w Bajtycy-Zdroju odbywa się impreza, na którą przybyły tłumy okolicznych mieszkańców. Organizowane są liczne zabawy, przed każdą z nich chłopcy dobierają się w pary z dziewczętami tak, by stworzyć jak największą liczbę par. Do jednej pary dobierają się jedynie takie dwie osoby, które znają się wzajemnie. To pozwala nam wprowadzić kluczowe dla tego zadania pojęcie:
Definicja. Duszą towarzystwa nazywamy osobę, której wyjście z imprezy spowoduje, że maksymalna możliwa do utworzenia liczba par chłopców i dziewcząt zmaleje.
Za chwilę ma się odbyć kolejna zabawa, jednak powstał problem. Do remizy przyszła o jedna osoba więcej niż pozwalają przepisy przeciwpożarowe. Trzeba więc znaleźć kogoś, kto w zamian za darmową wejściówkę na wszystkie kolejne imprezy w tym sezonie zgodzi się wrócić już do domu. Strażacy szybko postanowili, że wszystkie dusze towarzystwa lepiej zapytać w drugiej kolejności. Pomóż im i wyznacz wszystkie dusze towarzystwa obecne w remizie.
W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite , i (, ), oznaczające odpowiednio liczbę chłopców i dziewcząt oraz liczbę znajomości pomiędzy nimi. Chłopców i dziewczęta numerujemy kolejnymi liczbami całkowitymi, począwszy od . W kolejnych wierszach znajdują się opisy znajomości. Każdy z tych wierszy zawiera dwie liczby całkowite i (, ), które oznaczają, że chłopiec i dziewczę znają się wzajemnie.
Na standardowe wyjście wypisz numery wszystkich osób, które są duszami towarzystwa, w osobnych wierszach. Najpierw należy wypisać numery chłopców, a następnie numery dziewcząt. Obydwie listy numerów powinny być posortowane rosnąco.
Dla danych wejściowych:
4 4 4 2 1 3 2 4 3 4 4
poprawną odpowiedzią jest:
2 3 4 1 2
Autor zadania: Jakub Łącki (poniekąd zapożyczenie).