eolymp
bolt
Try our new interface for solving problems
Məsələlər

Bahalı metro

Bahalı metro

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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ə

Giriş verilənləri #1
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

Çıxış verilənləri #1
12
Impossible