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.