Метро#2795
Метросистема складається з ліній, з станціями, пронумерованими від до . Кожна станція може належати до однієї або декількох ліній. Якщо станція належить до кількох ліній, вона є пересадковою і дозволяє пересадки між цими лініями. Кожна лінія містить щонайменше дві станції і щонайменше одну пересадкову станцію. Метросистема є зв'язною, тобто існує маршрут між будь-якою парою станцій. Вартість поїздки визначається як мінімум серед наступних двох варіантів:
копійок за кожну станцію, використану під час маршруту, включаючи початкову і кінцеву станції.
копійок за кожну лінію, використану під час маршруту.
Визначте мінімальну кількість копійок, необхідну для поїздки зі станції до станції .
Перший рядок містить чотири натуральних числа: , , , та .
Наступні рядків містять послідовності номерів станцій, що відносяться до кожної лінії метро.
Останній рядок містить числа та , які вказують на початкову та кінцеву станції.
Усі числа — натуральні, L \leq 10, усі інші значення не перевищують .
Виведіть мінімальну кількість копійок, необхідну для цієї поїздки.
Приклад 1