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