e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Соревнования

Dijkstra algorithm

Метро

Схема метро состоит из n станций, размещенных на l линиях. Каждая станция принадлежит одной или более линиям (в этом случае на станции можно выполнить пересадку на любою из линий, которые через нее проходят). Каждая линия состоит из двух или более станций и пересекается хотя бы с одной другой линией. Схема метро связана.

Движение между двумя соседними станциями одной линии можно производить в любом направлении на протяжении 2 минут; на пересадку с линии на линию в пределах одной станции тратится 1 минута. Любыми другими затратами времени можно пренебречь.

Найти минимальное время, необходимое для того, чтобы менеджеру фирмы "Диез-продукт" добраться от станции a к зданию офиса компании, расположенного вблизи станции b.

Входные данные

В первой строке заданы два натуральных числа n и l (1l10). В следующих l строках записаны последовательные номера станций каждой из линий метро. В последней строке указаны номер и линия начальной и конечной станций. Все числа натуральные и не превышают 70.

Выходные данные

Вывести минимальное время движения между указанными станциями.

prb68.gif

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
7 3
2 1 3
6 1 4 5
5 7
2 1 7 3
Выходные данные #1
10