Metro
Cek dostu Mişeli ziyarət etməyə hazırlaşır. Atası ona bunu müstəqil şəkildə, metroya minərək etməyə icazə verib. Cek metroda səyahət etməyi sevir və bu fürsətdən istifadə edərək yarım gününü yeraltında keçirməkdən məmnundur, lakin atası metroda mümkün qədər az xətt dəyişdirməsini israr edir. Şəhərdə çoxlu stansiyalar və onları birləşdirən bir neçə xətt var. Bütün qatarların hərəkəti mükəmməl sinxronlaşdırılıb - hər xətt üzrə iki qonşu stansiya arasında səyahət müddəti dəqiq bir dəqiqə çəkir və hər hansı bir stansiyada xətt dəyişdirmək ani baş verir.
Verilmiş metro xəritəsinə əsasən Cekə səyahətini elə planlaşdırmağa kömək edin ki, səyahət müddəti maksimum olsun, lakin atasının göstərişi qüvvədə qalsın.
Giriş verilənləri
Birinci sətir testlərin sayını t ehtiva edir. Hər bir test aşağıdakı formatda olur:
Hər bir testin təsviri boş sətir ilə başlayır. Növbəti iki sətir Stops: və Lines: ifadələri ilə başlayır və bütün metro dayanacaqlarının və xətlərinin adlarını (vergüllə və boşluqla ayrılmış) ehtiva edir. Hər bir metro xətti bir sətirdə təsvir olunur (sırası vacib deyil), route: ifadəsi ilə başlayaraq xətt boyunca stansiyaların siyahısını verir. Son iki sətir Cek və Mişelin evlərinin yaxınlığındakı (fərqli) stansiyaların adlarını təyin edir.
Hər bir testdə ən çox 300000 stansiya və 100000 xətt var, ümumi uzunluğu 1000000-dən çox deyil. Stansiya və xətt adları 1 ilə 50 simvol arasında - hərflər, rəqəmlər, tire (-), apostroflar (') və "and" () simvollarını ehtiva edir. Bütün xətlər ikitərəflidir (baxmayaraq ki, hərəkət istiqamətinin dəyişdirilməsi xəttin dəyişdirilməsi kimi qəbul edilir) və öz-özünə kəsişməz.
Çıxış verilənləri
Testlərə cavabları verildiyi sırada çıxarın. Hər bir test üçün Cek üçün optimal marşrutu bir sətirdə çıxarın (dəqiq format üçün nümunəyə baxın). Belə bir marşrutun həmişə mövcud olduğunu hesab edin.