Wyspa
Limit pamięci: 32 MB
Bajtazar jest królem Bajtocji, wyspy na Oceanie Szczęśliwości.
Bajtocja ma kształt figury wypukłej, a wszystkie miasta w niej są położone nad brzegiem oceanu.
Jedno z tych miast to Bajtogród, stolica Bajtocji.
Każde dwa miasta są połączone drogą biegnącą przez wyspę po prostej łączącej oba miasta.
Drogi łączące różne pary miast przecinają się, tworząc skrzyżowania.
Bitocy, konkurent Bajtazara do tronu, zaplanował nikczemny spisek.
W trakcie podróży Bajtazara ze stolicy do sąsiedniego miasta opanował Bajtogród.
Bajtazar musi jak najszybciej powrócić do Bajtogrodu, by odzyskać władzę.
Niestety niektóre z dróg są patrolowane przez zbrojne bojówki Bitocego.
Bajtazar nie może poruszać się takimi drogami, choć może przekraczać je na skrzyżowaniach.
Na trasie może on skręcać wyłącznie na skrzyżowaniach.
Bajtazar wie, które drogi są patrolowane przez bojówki Bitocego.
Poprosił Cię o wyznaczenie najkrótszej bezpiecznej trasy z miasta, w którym się aktualnie
znajduje, do Bajtogrodu.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite i , oddzielone pojedynczym
odstępem (, ), oznaczające odpowiednio: liczbę miast oraz liczbę dróg
patrolowanych przez bojówki Bitocego.
Ponumerujmy miasta od 1 do , zaczynając od Bajtogrodu i idąc wzdłuż brzegu zgodnie z ruchem wskazówek zegara.
Bajtazar znajduje się w mieście nr .
W każdym z kolejnych wierszy znajduje się para liczb i
(),
oddzielonych pojedynczym odstępem, oznaczających współrzędne miasta nr na wyspie.
W każdym z kolejnych wierszy znajduje się para liczb i ().
Para taka oznacza, że droga łącząca miasta i jest patrolowana przez bojówki Bitocego.
Pary liczb opisujące patrolowane drogi nie powtarzają się.
Możesz założyć, że dla każdych danych testowych Bajtazar może dostać się do Bajtogrodu.
Wyjście
Twój program powinien wypisać na standardowe wyjście jedną liczbę zmiennopozycyjną:
długość najkrótszej bezpiecznej trasy prowadzącej z miasta do Bajtogrodu.
Wynik Twojego programu może różnić się od poprawnego o co najwyżej .
Przykład
Dla danych wejściowych:
6 9
-12 -10
-11 6
-4 12
6 14
16 6
18 -2
3 4
1 5
2 6
2 3
4 5
3 5
1 3
3 6
1 6
poprawną odpowiedzią jest:
42.0000000000
Trasa, którą powinien podążać Bajtazar, wychodzi z miasta 6 w kierunku miasta 4,
następnie biegnie drogą łączącą miasta 2 i 5, a na koniec drogą łączącą Bajtogród z miastem 4.
Autor zadania: Jakub Onufry Wojtaszczyk.