e-olymp

Metro

Metronun sxemi I xətt üzərində yerləşən n stansiyadan ibarətdir. Hər stansiya bir və ya daha çox xəttə aiddir(bu halda həmin stansiyada düşüb oradan keçən istənilən xəttə keçmək olar). Hər bir xətt iki və ya daha çox stansiyadan ibarətdir, heç olmasa digər bir xətlə kəsişir. Metronun sxemi əlaqəlidir.

Bir xətdəki iki qonşu stansiyaya arasında istənilən istiqamətdə hərəkətə 2 dəqiqə, bir stansiya daxilində bir xətdən digər xəttə keçməyə 1 dəqiqə vaxt sərf olunur. İstənilən digər vaxt itkilərini nəzərə almamaq olar.

“Diez-produkt” firması menecerinin a stansiyasından b stansiyasının yaxınlığında yerləşən kompaniyanın ofisinə çatması üçün zəruri olan ən az vaxtı tapın.

Giriş verilənləri:

Birinci sətirdə iki natural n I ədədləri verilir. Sonrakı I sayda sətirdə metronun hər xəttindəki stansiyaların nömrələri ardıcıl yazılır. Sonuncu sətirdə başlanğıc və son stansiyaların nömrələri göstərilir. Bütün ədədlərin qiymətləri naturaldır və 70-i aşmır (1 ≤I ≤ 10).

Çıxış verilənləri:

Yeganə ədəd – göstərilən stansiyalar arasında hərəkətə sərf edilən ən az vaxt verilir.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
7 3
2 1 3
6 1 4 5
5 7
2 1 7 3
Çıxış verilənləri #1
10