Эко-езда
Моя коллега Элизабет очень ленива - как на работе, так и когда идет на работу. Она никогда не хочет делать больше, чем это необходимо, это касается также ее поездок на работу. Ее цель состоит в использовании минимального количества энергии, поэтому она старается тормозить и ускоряться как можно меньше. Этот метод она применяет и для всех транспортных средств, которыми владеет.
Элизабет ранее оптимизировала свой маршрут путем проб и ошибок, но теперь нуждается в Вашей помощи чтобы найти оптимальный путь. Она предоставила карту с n перекрестками и r односторонними дорогами между перекрестками. Если дорога двусторонняя, то она представляется в виде двух односторонних дорог.
К счастью, Элизабет часто работает в ночную смену, так что торможение и ускорение необходимы ей только при поворотах на перекрестках, так как нет никакого другого движения на дорогах. Ее цель состоит в нахождении пути, на котором максимальный угол поворота на перекрестках сведен к минимуму, так как это максимизирует скорость. Тем не менее, маршрут не может быть слишком долгим.
Входные данные
Первая строка содержит три целых числа j (2 ≤ j ≤ 200), r (1 ≤ r ≤ 39800) и d (1 ≤ d ≤ 1000000). j - количество перекрестков, r - количество односторонних дорог между перекрестками, d - наибольшее расстояние в метрах, которое Элизабет согласна пройти. Дорожная сеть такова, что может не существовать такого пути, который сможет использовать Элизабет, длина которого равна l, что d < l < d · (1 + 10^(-6)).
Далее следует j строк с двумя целыми числами x и y (-100000 ≤ x, y ≤ 100000) - координатами различных перекрестков в метрах на плоской земле. Элизабет проживает на перекрестке 1, а работает на перекрестке j. Следующие r строк содержат два целых числа a и b. Они описывают одностороннюю дорогу между перекрестками a и b (1 ≤ a, b ≤ j).
Выходные данные
Вывести максимальный угол поворота на пути, который будет минимально возможным. Угол поворота выводить в грдусах с ошибкой не более 10^(−6). Если пути заданной длины не существует, вывести "Impossible".