Bahalı metro
Bahalı metro
Peter dünyanın ən bahalı şəhərlərindən biri olan Expensive City-də yaşayır. Peterin maşın almağa pulu yoxdur və Pahalı Şəhərdə avtobuslar olduqca pisdir, ona görə də işə getmək üçün metrodan istifadə edir. İndiyə qədər metro çox ucuz idi: sadəcə bir $2 biletlə istənilən yerə səyahət edə bilərsiniz. Keçən ay menecerlər bunun çox ucuz olduğuna qərar verdilər və onlar EFS (Bahalı Tarif Sistemi) icad etdilər. Bu sistemlə istifadəçilər yalnız qonşu stansiyalar arasında aylıq bilet ala bilərlər ki, bu da onlara bu stansiyalar arasında istənilən sayda hərəkət etməyə imkan verir. Aylıq biletin qiyməti stansiyalar arasında dəyişir, ona görə də hansı biletləri almaq qərarına diqqətlə yanaşmaq lazımdır.
Əvvəlki metro planı ilə Picadilly-dən Viktoriya və Queensway-ə səyahət etməyin ən ucuz yolu ümumi dəyəri $12 olan aylıq Picadilly-Victoria və Queensway-Victoria biletini almaq idi.
Peter satıcıdır, ona görə də şəhərin istənilən yerinə səyahət edə bilməlidir. O, mümkün qədər az pul xərcləmək istəyir və şəklə gəldiyiniz yer budur. O, sizi bir proqram yazmaq üçün işə götürdü ki, stansiyaların siyahısını, stansiya cütləri və Peterin evinə ən yaxın stansiya arasında aylıq biletlərin gediş haqqını nəzərə alaraq, Peterin başqa yerə səyahət etmək üçün xərclədiyi minimum pulu qaytarır. stansiya. Bu proqram həmçinin Peterin ev stansiyasından bütün qalanlara getmək mümkün olmadıqda dəyəri qaytarmalıdır, çünki bu halda Peter avtobuslardan istifadə etməyi düşünməyə başlayacaq...
Giriş verilənləri
Giriş bir neçə test vəziyyətindən ibarətdir. Test işi iki tam ədəddən ibarət sətirlə başlayır: 1 \le s \le 400 (stansiyaların sayı) və 0 \le c \le 79800 (qoşulmaların sayı) bir boşluqla ayrılır. Bunun ardınca hər birində bir metro stansiyasının adı olan xətlər gəlir. Bu adlar durğu işarələri və ya boşluq simvolları olmayan simvol sətirləri (böyük və ya kiçik hərflər) və maksimum 10 simvol uzunluğunda olacaq. Stansiyaların adlarından sonra stansiyalar arasında əlaqəni göstərən c sətirləri olacaq. Bağlantı insanlara hər iki istiqamətdə bir stansiyadan digərinə səyahət etməyə imkan verir. Hər bir əlaqə stansiyaların adlarını göstərən iki sətir və aylıq biletin qiymətini göstərən müsbət tam ədəd kimi təmsil olunur, bunların hamısı tək boşluqlarla ayrılır. Əlaqələrdə görünən bütün stansiya adları əvvəllər stansiyaların siyahısında görünəcək. Əlaqələrin hamısı fərqli olacaq və stansiyadan özünə heç bir əlaqə olmayacaq. Test işi Peterin bütün digər stansiyalara getməli olduğu stansiyanın adını ehtiva edən sətirlə başa çatacaq.
Daxiletmə fantom test qutusu 0\ 0 ilə başa çatır, onu emal etmək olmaz.
Çıxış verilənləri
Hər bir sınaq işi üçün çıxış tam ədədi, Peterin verilmiş stansiyadan bütün digərlərinə səyahət etmək üçün ödədiyi minimum aylıq qiyməti və ya bütün stansiyalara səyahət etmək mümkün olmadıqda Mümkün deyil
olan sətir olacaq. stansiyalar.
Nümunə
3 3 Picadilly Victoria Queensway Picadilly Victoria 2 Queensway Victoria 10 Queensway Picadilly 20 Picadilly 4 2 Picadilly Victoria Queensway Temple Picadilly Victoria 2 Temple Queensway 100 Temple 0 0
12 Impossible