Zosia
Limit pamięci: 128 MB
Mała Zosia urządza przyjęcie urodzinowe.
Sporządziła wstępną listę swoich znajomych z przedszkola,
których chciałaby zaprosić.
Dzieci są jednak bardzo wymagające.
Maja powiedziała, że przyjdzie, ale tylko jeśli na przyjęciu
nie będzie Kamilki i Emilki, które w zeszłym tygodniu zabrały jej lalkę.
Mały Krzyś bawi się tylko z Zosią oraz Kamilką, i nie chce widzieć
na przyjęciu innych dzieci.
I tak dalej
Zosia mówi, że przyjęcie jest udane, jeżeli żaden spośród gości
nie ma nic przeciwko obecności pozostałych gości.
Zosia postanowiła, że nie zaprosi niektórych dzieci, aby przyjęcie
było udane.
Z drugiej strony, Zosia chciałaby zaprosić jak najwięcej dzieci.
Uznała, że jeśli nie będzie mogła zaprosić przynajmniej dzieci,
to w ogóle nie urządzi przyjęcia.
Zadanie
Pomóż małej Zosi!
Napisz program, który:
-
wczyta ze standardowego wejścia liczbę wszystkich
znajomych Zosi, liczbę oraz opis wymagań dzieci,
-
sprawdzi, czy można zaprosić co najmniej dzieci
tak, aby przyjęcie było udane,
-
jeżeli nie jest to możliwe, to wypisze na standardowe wyjście
słowo NIE;
jeżeli jest to możliwe, to znajdzie i
wypisze na standardowe wyjście najliczniejszą grupę
dzieci, które można zaprosić na przyjęcie, tak aby było ono
udane.
Wejście
Pierwszy wiersz standardowego wejścia zawiera
dwie liczby całkowite nieujemne, oddzielone pojedynczym odstępem:
- liczbę wszystkich znajomych Zosi (),
- minimalną liczbę dzieci, które Zosia chce zaprosić na
przyjęcie ().
Dzieci są ponumerowane liczbami od do .
Kolejne wiersze zawierają opis wymagań dzieci.
W drugim wierszu znajduje się jedna liczba całkowita ,
.
Każdy z kolejnych wierszy zawiera parę liczb całkowitych
, oddzielonych pojedynczym odstępem
(, ).
Możesz założyć, że każda para (uporządkowana)
pojawia się na wejściu co najwyżej raz.
Para oznacza, że dziecko o numerze nie chce spotkać
na przyjęciu dziecka o numerze .
Wyjście
Jeżeli nie jest możliwe zaproszenie na przyjęcie dzieci, tak
aby było ono udane, to pierwszy i jedyny
wiersz standardowego wyjścia powinien zawierać tylko jedno
słowo: NIE.
Jeżeli jest to możliwe, to pierwszy wiersz standardowego wyjścia
powinien zawierać jedną liczbę całkowitą - maksymalną liczbę
dzieci, które można zaprosić na przyjęcie, tak aby było ono
udane.
Drugi wiersz standardowego wyjścia powinien wówczas zawierać
numery dzieci, które należy zaprosić, podane w rosnącej
kolejności i pooddzielane pojedynczymi odstępami.
Jeżeli istnieje wiele poprawnych wyników, Twój program powinien
wypisać dowolny z nich.
Przykład
Dla danych wejściowych:
9 4
12
9 6
4 6
7 9
1 2
2 1
9 7
7 6
4 5
7 8
8 9
3 4
4 3
poprawną odpowiedzią jest:
5
1 3 5 6 8
Autor zadania: Łukasz Kowalik.