In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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.
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 .
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.
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.