Astmatyk
To zadanie pochodzi z Kółka Informatycznego w Staszicu.
autor: Piotr Cerobski
Bajtazar jest miłośnikiem wycieczek górskich. Niestety cierpi na astmę i gdy wejdzie na zbyt dużą wysokość to zaczyna się dusić. Z tego powodu musi bardzo dokładnie planować swoje wyprawy. Jednak nie jest to proste. Bajtazar posiada bardzo dokładne mapy gór z dziesiątkami tysięcy szlaków, każdy szlak zaczyna się na pewnej wysokości i na jakiejś kończy. Nasz bohater ustalił miejsce skąd wyrusza i dokąd się kieruje jednak przytłoczony ilością informacji za bardzo sobie nie radzi z ułożeniem optymalnej trasy.
Zadanie
Pomóż Bajtazarowi w ułożeniu wycieczki. Napisz program który wczyta opis gór (punkty na różnych wysokościach połączone szlakami) i powie na jaką minimalną wysokość musi wejść Bajtazar aby dojść do wyznaczonego miejsca.
Wejście
W pierwszym wierszu znajdują się liczby N i M (1<=N<=100000; 1<=M<=300000), które oznaczają odpowiednio ilość punktów na mapie i ilość szlaków. W następnych N wierszach znajdują się wysokości na których leżą punkty. Wysokości to liczby całkowite z przedziału 1..1000000. W K+1 wierszu znajduje się wysokość K-tego wierzchołka. W każdym z następnych M wierszy znajduje się opis szlaku. Składa się on z dwóch liczb A B, które mówią, iż szlak ten prowadzi od punktu A do punktu B. Po szlakach można chodzić w obie strony i można założyć że wysokość, na której leży szlak mieści się między wysokością A i B.
Wyjście
Twój program powinien wypisać minimalną wysokość, na którą musi wejść Bajtazar, aby przejść po szlakach z wierzchołka 1 do wierzchołka n. Możesz założyć, że jakaś droga zawsze istnieje.
Przykład
Dla danych wejściowych:
9 11 3 10 9 6 8 3 2 4 1 1 2 1 3 7 1 4 1 4 6 5 3 6 7 7 8 8 9 6 9 5 9
program powinien wypisać liczbę:
3
(jest to droga 1-7-6-9)