Wycieczka
Limit pamięci: 32 MB
Grupa turystów ma sposobność zwiedzić wiele pięknych miast.
Każdy uczestnik grupy może wskazać dwa miasta i o każdym z nich powiedzieć, czy chce lub nie chce je odwiedzić.
Może się zdarzyć, że turysta wskaże dwa razy to samo miasto i raz będzie chciał je odwiedzić, a raz nie.
Zadanie
Napisz program, który:
- wczytuje ze standardowego wejścia opisy wskazań turystów,
- sprawdza, czy można sporządzić listę miast, których odwiedzenie sprawi, że co najmniej jedno życzenie każdego turysty zostanie spełnione (lista może być pusta),
- wypisze na standardowe wyjście listę miast zadowalającą wszystkich turystów.
W przypadku wielu możliwych wyników Twój program powinien podać którykolwiek z nich.
Wejście
Pierwszy wiersz danych zawiera dwie dodatnie liczby całkowite
i (, );
jest liczbą turystów, natomiast jest liczbą miast.
Turyści są ponumerowani od do , natomiast miasta są ponumerowane od do .
Każdy z następnych wierszy zawiera dwie niezerowe liczby całkowite oddzielone pojedynczym odstępem.
W -tym z tych wierszy znajdują się liczby i , odddzielone pojedynczym
odstępem, opisujące życzenia -tego turysty, , ,
, .
Liczba dodatnia oznacza, że turysta chce odwiedzić miasto o tym numerze, natomiast liczba ujemna oznacza, że turysta nie chce odwiedzić miasta o numerze równym wartości bezwględnej tej liczby.
Wyjście
W pierwszym wierszu Twój program powinien zapisać jedną nieujemną liczbę całkowitą , oznaczającą liczbę miast do odwiedzenia.
Drugi wiersz powinien zawierać dodatnich liczb całkowitych uporządkowanych rosnąco - numery miast, które należy odwiedzić, żeby zadowolić wszystkich turystów.
W przypadku, gdy nie można utworzyć listy miast zadowalających wszystkich turystów (być może pustej), Twój program powinien zapisać w pierwszym i jedynym wierszu wyjścia słowo NO.
Przykład
Dla danych wejściowych:
3 4
1 -2
2 4
3 1
poprawną odpowiedzią jest:
2
3 4