Śmieci
Limit pamięci: 256 MB
Przedsiębiorstwo Oczyszczania Bajtogrodu (POB) podniosło drastycznie ceny za wywóz śmieci. Część mieszkańców zrezygnowała z płacenia za wywóz śmieci i zaczęła wyrzucać je na ulice. W rezultacie wiele ulic Bajtogrodu tonie w śmieciach.
Sieć drogowa Bajtogrodu składa się z skrzyżowań, z których niektóre połączone są dwukierunkowymi ulicami.
Żadne dwie ulice nie łączą tej samej pary skrzyżowań.
Niektóre z ulic są zaśmiecone, podczas gdy inne nie.
Burmistrz Bajtogrodu, Bajtazar, zdecydował się na niekonwencjonalną akcję mającą skłonić mieszkańców do płacenia za wywóz śmieci. Postanowił on oczyścić tylko niektóre ulice miasta - te, przy których większość mieszkańców opłaciła wywóz śmieci. Natomiast te ulice, przy których większość mieszkańców nie opłaciła wywozu śmieci, postanowił pozostawić zaśmiecone lub - jeśli to konieczne - zwieźć na nie śmieci z innych ulic! Bajtazar przygotował plan miasta, na którym zaznaczył, które ulice docelowo powinny być czyste, a które zaśmiecone. Niestety, pracownicy POB-u nie są w stanie ogarnąć planu Bajtazara. Są jednak w stanie wykonywać niezbyt skomplikowane zlecenia.
Pojedyncze zlecenie polega na wykonaniu kursu śmieciarką, rozpoczynającego się na dowolnie wybranym skrzyżowaniu, prowadzącego określonymi ulicami i kończącego się na tym samym skrzyżowaniu, na którym zaczął się kurs. Przy tym, każde skrzyżowanie może w jednym kursie zostać odwiedzone co najwyżej raz, z wyjątkiem skrzyżowania, od którego kurs się rozpoczął i na którym się kończy (na którym śmieciarka pojawia się dokładnie dwa razy). Śmieciarka, jadąc zaśmieconą ulicą, sprząta ją, jadąc zaś czystą ulicą, wręcz przeciwnie - zaśmieca ją, wyrzucając śmieci.
Bajtazar zastanawia się, czy może zrealizować swój plan, zlecając ileś kursów śmieciarki. Pomóż mu i napisz program, który wyznaczy zestaw takich kursów lub stwierdzi, że nie jest to możliwe.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oddzielone pojedynczym odstępem:
i
(
,
),
oznaczające odpowiednio liczbę skrzyżowań oraz liczbę ulic w Bajtogrodzie.
Skrzyżowania są ponumerowane od
do
.
W kolejnych
wierszach znajdują się opisy kolejnych ulic, po jednej w wierszu.
W każdym z tych wierszy znajdują się po cztery liczby całkowite oddzielone pojedynczymi odstępami:
,
,
i
(
,
).
Taka czwórka oznacza, że skrzyżowania
i
są połączone ulicą,
przy czym
oznacza obecny stan zaśmiecenia ulicy (
oznacza czystą, a
zaśmieconą),
zaś
stan docelowy według planu Bajtazara.
Możesz założyć, że jeśli istnieje zestaw kursów realizujący plan Bajtazara, to
istnieje również taki zestaw, w którym łączna liczba ulic,
którymi prowadzą kursy śmieciarki, nie przekracza .
W testach wartych 60% punktów zachodzi dodatkowo ograniczenie .
Wyjście
Jeżeli za pomocą kursów śmieciarką nie da się zrealizować planu Bajtazara, to
pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać słowo "NIE".
W przeciwnym razie na wyjściu należy wypisać dowolny zestaw kursów
realizujący plan Bajtazara, w którym łączna liczba ulic, którymi prowadzą kursy, nie przekracza .
Pierwszy wiersz wyjścia powinien zawierać
: liczbę kursów w zestawie.
W kolejnych
wierszach powinny znaleźć się opisy kolejnych kursów, po jednym w wierszu.
Wiersz
-szy powinien zaczynać się dodatnią liczbą
oznaczającą liczbę ulic, którymi prowadzi
-ty kurs.
Po pojedynczym odstępie powinno znaleźć się
numerów kolejnych skrzyżowań, przez które prowadzi kurs,
pooddzielanych pojedynczymi odstępami.
Przykład
Na rysunkach cienką linią zaznaczono ulice, które są czyste, a grubą te, które są zaśmiecone. Linią przerywaną zaznaczono ulice, które docelowo powinny być czyste, a ciągłą te, które docelowo powinny być zaśmiecone.
Dla danych wejściowych:
6 8 1 2 0 1 2 3 1 0 1 3 0 1 2 4 0 0 3 5 1 1 4 5 0 1 5 6 0 1 4 6 0 1
jednym z poprawnych wyników jest:
2 3 1 3 2 1 3 4 6 5 4
natomiast dla danych wejściowych:
6 8 1 2 0 1 2 3 1 0 1 3 0 1 2 4 0 0 3 5 1 1 4 5 0 1 5 6 0 1 4 6 0 0
poprawnym wynikiem jest:
NIE
Autor zadania: Michał Pilipczuk.