Sola dönün
Taro universitet illərində böyük çətinliklə sürücülük vəsiqəsi aldı, lakin təəssüf ki, maşın sürmək imkanı olmadı. Nəticədə qızıl vəsiqə əldə etdi.
Bir gün o və dostları sizinlə birlikdə Kiotoya səyahət planlaşdırdılar. Görüşün sonunda onlar maşınla getməyə razılaşdılar, lakin böyük bir problem var idi; dostlarının heç biri maşın sürə bilmirdi. Beləliklə, Taro sürücü olmaq məcburiyyətində qaldı.
Yola düşmə günü gəldi. O, maşın sürəcək, lakin əks zolağa keçməkdən qorxduğu üçün heç vaxt sağa dönməyəcək (Yaponiyada maşınlar soldan gedir). Üstəlik, texnikası çatışmadığı üçün U-dönüş edə bilmir. Maşın naviqasiya sistemi ilə təchiz olunub, lakin sistem sağa dönmədən marşrut axtara bilmir. Beləliklə, sizdən xahiş etdi: "Sağa dönməkdən nifrət edirəm, ona görə də bu naviqasiya sistemindən götürülmüş yol xəritəsindən istifadə edərək təyinat yerinə yalnız sola dönməklə ən qısa marşrutu tapmaq üçün proqram yaza bilərsinizmi?"
Giriş verilənləri
Giriş bir neçə məlumat dəstindən ibarətdir. Girişin ilk sətri məlumat dəstlərinin sayını ehtiva edir. Hər bir məlumat dəsti aşağıdakı formatda təsvir olunur:
m n
name_1 x_1 y_1
...
name_m x_m y_m
p_1 q_1
...
p_n q_n
src dst
m kəsişmələrin sayıdır. n yolların sayıdır. namei i-ci kəsişmənin adıdır. (x_i, y_i) i-ci kəsişmənin tam koordinatlarıdır, burada müsbət x şərqə, müsbət y isə şimala gedir. p_j və q_j j-ci yolun son nöqtələrini təmsil edən kəsişmə adlarıdır. Bütün yollar ikitərəfli və ya şaquli, ya da üfüqidir. src və dst müvafiq olaraq mənbə və təyinat kəsişmələrinin adlarıdır. Aşağıdakıları qəbul edə bilərsiniz:
2 ≤ m ≤ 1000, 0 ≤ x_i ≤ 10000, və 0 ≤ yi ≤ 10000;
hər bir kəsişmə adı ən çox 25 simvol uzunluğunda bir və ya daha çox əlifba simvolundan ibarət ardıcıllıqdır;
heç bir kəsişmə eyni koordinatları paylaşmır;
heç bir yol cütü son nöqtələrindən başqa ümumi nöqtələrə malik deyil;
heç bir yolun ortasında kəsişmə yoxdur;
heç bir kəsişmə cütü bir yoldan artıq yola malik deyil;
Taro maşını istənilən istiqamətdə başlaya bilər; və
mənbə və təyinat kəsişmələri fərqlidir.
Qeyd edək ki, giriş məlumatlarında bir kəsişmənin üçdən az yolla bağlı olduğu bir vəziyyət ola bilər; yol xəritəsi yerli olmayan insanlar üçün uyğun olmayan kiçik yolları əhatə etməyə bilər. Belə bir halda, siz hələ də onlardan keçərkən onları kəsişmə kimi nəzərə almalısınız.
Çıxış verilənləri
Hər bir məlumat dəsti üçün Taro sağa dönmədən ən qısa məsafə marşrutunu sürdüyü zaman ən azı neçə dəfə kəsişmələrdən keçməli olduğunu çap edin. Mənbə və təyinat kəsişmələri Taro mənbədən başladıqda və ya təyinat yerinə çatdıqda "keçildi" kimi nəzərə alınmalıdır (beləliklə, sayılmalıdır). Həmçinin qeyd edək ki, bir neçə ən qısa marşrut mümkün ola bilər. Əgər sağa dönmədən təyinat yerinə marşrut yoxdursa, "impossible" çap edin.