Еко-їзда#6831
Моя колега Елізабет дуже лінива — як на роботі, так і коли йде на роботу. Вона ніколи не хоче робити більше, ніж це необхідно, і це стосується також її поїздок на роботу. Її мета — використовувати мінімальну кількість енергії, тому вона намагається гальмувати і прискорюватися якомога менше. Цей підхід вона застосовує до всіх транспортних засобів, якими володіє.
Раніше Елізабет оптимізувала свій маршрут методом проб і помилок, але тепер їй потрібна ваша допомога, щоб знайти оптимальний шлях. Вона надала карту з перехресть і односторонніми дорогами між ними. Якщо дорога двостороння, то вона представлена у вигляді двох односторонніх доріг.
На щастя, Елізабет часто працює в нічну зміну, тому гальмування і прискорення їй потрібні тільки при поворотах на перехрестях, адже на дорогах немає іншого руху. Її мета — знайти шлях, на якому максимальний кут повороту на перехрестях зведений до мінімуму, оскільки це максимізує швидкість. Однак маршрут не може бути занадто довгим.
Перша строка містить три цілі числа (2 \leq j \leq 200), (1 \leq r \leq 39800) і (1 \leq d \leq 1000000). — кількість перехресть, — кількість односторонніх доріг між перехрестями, — найбільша відстань у метрах, яку Елізабет згодна пройти. Дорожня мережа така, що може не існувати шляху, який Елізабет може використати, довжина якого дорівнює , де d < l < d \cdot (1 + 10^{-6}).
Далі йдуть рядків з двома цілими числами і (-100000 \leq x, y \leq 100000) — координатами різних перехресть у метрах на плоскій землі. Елізабет проживає на перехресті , а працює на перехресті . Наступні рядків містять два цілі числа і . Вони описують односторонню дорогу між перехрестями і (1 \leq a, b \leq j).
Виведіть максимальний кут повороту на шляху, який буде мінімально можливим. Кут повороту виводьте в градусах з похибкою не більше 10^{-6}. Якщо шляху заданої довжини не існує, виведіть "Impossible".
Приклад 1
Приклад 2