Dusza towarzystwa

Limit pamięci: 32 MB

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.

Wejście

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.

Wyjście

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.

Przykład

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).