Удав
Ensk şəhərinin zooparkından bir boa ilanı qaçıb. Təqibdən qaçaraq, o, yerli kanalizasiyaya girib. Kanalizasiya, bir-birinə düz üfüqi borularla birləşdirilmiş quyular dəstəsindən ibarətdir və bütün quyular, ikisi istisna olmaqla, qapaqlarla örtülüdür. Açıq quyulardan birinə boa girib və digər açıq quyudan çıxmaq istəyir. Bu zaman o, əlbəttə, ən qısa məsafəni keçmək istəyir. Həmçinin, boa artıq yaşlıdır və revmatizmdən əziyyət çəkir, o, maksimum α bucağına qədər əyilə bilər (başqa sözlə, boa bir borudan digərinə keçərkən hərəkət istiqaməti maksimum α bucağına qədər dəyişə bilər). Açıq quyulardan birindən digərinə ən qısa marşrutu müəyyən etmək lazımdır ki, bu marşrut maksimum α bucağına qədər əyilə bilsin (nümunəyə bax). Boa bir borudan digərinə yalnız hər iki borunun sonu olan quyuda keçə bilər. Boru boyunca boa istənilən istiqamətdə sürünə bilər.
Giriş verilənləri
Giriş faylının birinci sətirində boşluqla ayrılmış üç tam ədəd – N, M və α (1 < N ≤ 50, 0 ≤ M ≤ 1225, 0 ≤ α ≤ 180), burada N – quyuların sayı, M – bu quyuları birləşdirən boruların sayıdır. Növbəti sətirdə marşrutun başlanğıc və son quyularının nömrələri yazılıb. Sonra N sətirdə quyuların koordinatları yazılıb (modulu 10000-dən çox olmayan iki tam ədəd). Növbəti M sətirdə borular haqqında məlumat yazılıb – müvafiq boru ilə birləşdirilmiş quyuların nömrələrini göstərən iki ədəd. Quyular birdən başlayaraq nömrələnib.
Çıxış verilənləri
Çıxış faylının birinci sətirində bir ədəd – üç ondalık dəqiqliklə ən qısa marşrutun uzunluğunu və ya belə bir marşrut mövcud deyilsə –1 yazmaq lazımdır. Əgər marşrut mövcuddursa, növbəti sətirdə bu marşrutun quyularının nömrələrini ardıcıl olaraq boşluqla ayıraraq yazmaq lazımdır.