e-olymp
Змагання

July 9 - ADA Training

Метро

Схема метро складається з 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