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.