Eko-sürüş
Mənim həmkarım Elizabet çox tənbəldir - həm işdə, həm də işə gedərkən. O, heç vaxt lazım olandan artıq iş görmək istəmir, bu, onun işə gedib-gəlməsinə də aiddir. Onun məqsədi minimal enerji sərf etməkdir, buna görə də o, mümkün qədər az əyləc və sürətlənməyə çalışır. Bu metodu o, sahib olduğu bütün nəqliyyat vasitələrinə tətbiq edir.
Elizabet əvvəllər sınaq və səhvlər yolu ilə marşrutunu optimallaşdırmışdı, lakin indi optimal yolu tapmaq üçün sizin köməyinizə ehtiyacı var. O, n kəsişmə və kəsişmələr arasında r birtərəfli yollar olan xəritəni təqdim etdi. Əgər yol ikitərəflidirsə, o, iki birtərəfli yol şəklində təqdim olunur.
Xoşbəxtlikdən, Elizabet tez-tez gecə növbəsində işləyir, belə ki, əyləc və sürətlənmə yalnız kəsişmələrdə dönərkən lazımdır, çünki yollarda başqa hərəkət yoxdur. Onun məqsədi kəsişmələrdə maksimum dönmə bucağını minimuma endirməkdir, çünki bu, sürəti maksimuma çatdırır. Bununla belə, marşrut çox uzun ola bilməz.
Giriş məlumatları
Birinci sətir üç tam ədəd j (2 ≤ j ≤ 200), r (1 ≤ r ≤ 39800) və d (1 ≤ d ≤ 1000000) ehtiva edir. j - kəsişmələrin sayı, r - kəsişmələr arasında birtərəfli yolların sayı, d - Elizabetin getməyə razı olduğu maksimum məsafədir. Yol şəbəkəsi elədir ki, Elizabetin istifadə edə biləcəyi, uzunluğu l olan bir yol mövcud olmaya bilər ki, d < l < d · (1 + 10^(-6)).
Daha sonra j sətir iki tam ədəd x və y (-100000 ≤ x, y ≤ 100000) - düz yerdə metrlə müxtəlif kəsişmələrin koordinatlarını ehtiva edir. Elizabet 1 nömrəli kəsişmədə yaşayır və j nömrəli kəsişmədə işləyir. Növbəti r sətir iki tam ədəd a və b ehtiva edir. Onlar a və b kəsişmələri arasında birtərəfli yolu təsvir edir (1 ≤ a, b ≤ j).
Çıxış məlumatları
Yol üzərində minimum mümkün olan maksimum dönmə bucağını çıxarın. Dönmə bucağını 10^(−6) dəqiqliklə dərəcələrlə çıxarın. Əgər verilmiş uzunluqda yol mövcud deyilsə, "Impossible" çıxarın.