Autobus

Limit pamięci: 32 MB

W związku z nadchodzącymi wyborami, władze Bajtogrodu postanowiły uruchomić nową linię autobusową.

W Bajtogrodzie jest skrzyżowań oraz jednokierunkowych ulic łączących te skrzyżowania. Każda ulica ma kształt odcinka łączącego dwa skrzyżowania (nie ma na niej żadnych łuków, skrętów itd.). Skrzyżowania to jedyne miejsca, gdzie można zjechać z ulicy na inną - jeśli dwie ulice się krzyżują, a nie ma tam skrzyżowania, to prawdopodobnie jedna prowadzi tunelem albo wiaduktem; jeśli natomiast dwie ulice się pokrywają, to prawdopodobnie jedna prowadzi estakadą. Dwa skrzyżowania mogą być połączone przez wiele dróg - takie drogi uważane są wówczas za różne.

Prace posuwały się na początku szybko - bez problemu ustalono, jaki jest czas przejazdu autobusu przez każdą ulicę (okazało się, że wartość ta wyrażała się dla każdej ulicy parzystą liczbą minut), na których ulicach trzeba ustawić przystanki (przystanek zawsze stoi dokładnie w połowie ulicy, czyli od początku ulicy do przystanku autobus jedzie tak samo długo, jak od przystanku do końca ulicy) oraz w jakiej kolejności autobus ma je odwiedzać.

Dalej jednak zaczęły się schody.

Po pierwsze, okazało się, że autobus jest mało zwrotny, i może na skrzyżowaniach wykonywać skręty tylko wtedy, kiedy kąt skrętu jest nie większy niż .

Jeżeli autobus jedzie w kierunku zgodnym ze strzałką, to oznacza jego kąt skrętu.

Po drugie, nikt w Bajtogrodzkim Urzędzie Miasta nie potrafi znaleźć optymalnej trasy dla autobusu, minimalizującej czas przejazdu autobusu z pierwszego do ostatniego przystanku. Twój przyjaciel, który pracuje w Urzędzie, poprosił Cię o pomoc. Pomóż mu ułożyć optymalną trasę! Możemy przyjąć, że autobus w ogóle się nie zatrzymuje na przystankach (z dodaniem czasu na postój urzędnicy już sobie poradzą), lecz wystarczy, jeżeli przejedzie koło każdego z nich.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis Bajtogrodu oraz zamierzonych przystanków,
• wyznaczy optymalną trasę autobusu,
• wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz wejścia zawiera trzy liczby całkowite , i (, , ), pooddzielane pojedynczymi odstępami - liczbę skrzyżowań w Bajtogrodzie, liczbę ulic i liczbę zamierzonych przystanków.

Kolejne wierszy opisuje skrzyżowania. W -szym wierszu wejścia znajdują się dwie liczby całkowite i (), oddzielone pojedynczym odstępem - współrzędne -tego skrzyżowania. Skrzyżowania są ponumerowane od do .

Następne wierszy zawiera informacje o kolejnych ulicach. W -szym wierszu znajdują się trzy liczby całkowite - , oraz (, , ), pooddzielane pojedynczymi odstępami. Oznaczają one, że -ta ulica prowadzi ze skrzyżowania do i czas przejazdu po tej ulicy wynosi . Ulice są ponumerowane od do .

W kolejnych wierszach znajduje się po jednej liczbie całkowitej; w wierszu -szym znajduje się () - numer ulicy, przy której ma się znaleźć -ty przystanek. Numery ulic mogą się powtarzać - jeśli , to oznacza, że po odwiedzeniu przystanków na ulicach autobus ma wrócić na przystanek przy ulicy . W szczególności, jeżeli , to autobus powinien odjechać z przystanku , a następnie wrócić do niego.

Wyjście

Jeśli nie istnieje trasa spełniająca wymogi Urzędu, to należy wypisać tylko jedno słowo NIE. W przeciwnym przypadku należy wypisać wierszy. W -tym wierszu powinien się znaleźć czas przyjazdu autobusu na -szy przystanek (licząc od odjazdu z przystanku pierwszego), przy założeniu, że autobus jedzie optymalną trasą.

Przykład

Dla danych wejściowych:

4 6 3
-1 -1
1 -1
1 1
-1 1
1 2 1
2 3 2
3 4 3
4 1 5
2 4 1
1 3 2
1
4
3

poprawną odpowiedzią jest:

16
30

Na rysunku kółkami oznaczono skrzyżowania, a kwadratami - przystanki. Cienkimi kreskami oznaczono ulice, natomiast grubą - najlepszą możliwą trasę z pierwszego przystanku na drugi, czyli pierwszy fragment optymalnej trasy autobusu. Dla uproszczenia na rysunku pominięto czasy przejazdu przez poszczególne ulice.

Autor zadania: Szymon Wrzyszcz.