Mosty

Limit pamięci: 64 MB

San Bajcisko to pięknie położone nadmorskie miasto. Składa się ono z niewielkich, ale gęsto zaludnionych wysp, ponumerowanych od do . Pewne pary wysp są połączone mostami, którymi poprowadzono dwukierunkowe drogi. Każda para wysp może być połączona co najwyżej jednym mostem. Z każdej wyspy San Bajciska można dotrzeć do dowolnej innej, przemieszczając się pomiędzy wyspami wyłącznie za pomocą mostów.

Bajtazar i Bajtek wybierają się na przejażdżkę rowerową po San Bajcisku. Swoją wycieczkę zaczną na wyspie nr 1. Chcą zwiedzić miasto, przejeżdżając każdym mostem dokładnie raz, i zakończyć podróż na wyspie nr . Niestety, w wycieczce będzie im przeszkadzał... wiatr. Otóż na każdym moście strasznie wieje, co w różnym stopniu może utrudniać przejazd rowerowy mostem w jedną bądź w drugą stronę. Dla uproszczenia zakładamy, że przy ustalonym kierunku przejazdu przez dany most siła wiatru jest stała.

Pomóż Bajtazarowi i Bajtkowi znaleźć taką trasę spełniającą ich wymagania, po przejechaniu której będą najmniej zmęczeni. Jako miarę tego, na ile trasa jest męcząca, przyjmujemy maksymalną siłę wiatru, z jaką nasi bohaterowi będą musieli zmagać się na trasie.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oddzielone pojedynczym odstępem: oraz (, ), oznaczające odpowiednio liczbę wysp oraz liczbę mostów w San Bajcisku. Wyspy są ponumerowane od 1 do , a mosty od 1 do . W kolejnych wierszach znajdują się opisy mostów. -szy wiersz zawiera cztery liczby całkowite , , , (, , ), pooddzielane pojedynczymi odstępami. Liczby te opisują most nr łączący wyspy o numerach oraz . Siła wiatru, jaki przeszkadza w trakcie przejazdu rowerem z wyspy do , to ; jeżeli zaś przejechać tym samym mostem z wyspy do , to przeszkadzający wiatr będzie miał siłę .

Wyjście

Jeżeli nie istnieje żadna trasa spełniająca wymagania naszych bohaterów, to pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedno słowo NIE. W przeciwnym przypadku wyjście powinno składać się z dwóch wierszy, opisujących najmniej męczącą trasę wycieczki po San Bajcisku. Pierwszy z nich powinien zawierać jedną liczbę całkowitą: największą siłę wiatru, jaki będzie wiał w trakcie wycieczki. Właśnie tę liczbę należy zminimalizować. W drugim wierszu powinno znaleźć się liczb całkowitych, pooddzielanych pojedynczymi odstępami i oznaczających numery mostów, którymi kolejno przejeżdża się na najmniej męczącej trasie.

Jeśli istnieje więcej niż jedna poprawna odpowiedź, Twój program powinien wypisać dowolną z nich.

Przykład

Dla danych wejściowych:

4 4
1 2 2 4
2 3 3 4
3 4 4 4
4 1 5 4

poprawną odpowiedzią jest:

4
4 3 2 1

Wyjaśnienie do przykładu: Optymalna trasa Bajtazara i Bajtka ma postać: . Maksymalna siła wiatru na tej trasie wynosi .

Autorzy zadania: Szymon Acedański, Jakub Radoszewski.