eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Метро

Метро

Ліміт часу 5 секунд
Ліміт використання пам'яті 256 MiB

Джони собирается навестить своего друга Мишеля. Отец позволил ему это сделать самостоятельно, отправившись на метро. Джони любит ездить на метро и с удовольствием использует эту возможность чтобы провести полдня под землей, однако отец настоял на том чтобы он сменил в метро как можно меньше линий. В городе имеется много станций, а также несколько линий, соединяющих их. Движение всех поездов идеально синхронизировано – время проезда между двумя соседними станциями на каждой линии занимает в точности одну минуту, а смена линий на любой станции происходит мгновенно.

По заданной карте метро помогите Джону так спланировать его поездку, чтобы время путешествия было наибольшим, но при этом в силе оставалось указание отца.

Вхідні дані

Первая строка содержит количество тестов t. Каждый тест имеет следующий формат:

Описание каждого теста начинается с пустой строки. Следующие две строки начинаются фразами Stops: и Lines:, и содержат названия (разделенные запятыми и пробелами) всех остановок метро и линий. Каждая линия метро описывается в одной строке (не важно в каком порядке), начинаясь фразой route: с дальнейшим перечислением станций вдоль линии. Последние две строки задают названия (разных) станций возле домов Джони и Мишеля.

В каждом тесте не более 300000 станций и 100000 линий, общая длина которых не превышает 1000000. Названия станций и линий содержат от 1 до 50 символов - букв, цифр, дефисов (-), апострофов (') и символов "and" (). Все линии двунаправленные (хотя изменение направления движения считается как изменение линии) и без самопересечений.

Вихідні дані

Выведите ответы к тестам в том же порядке в котором они заданы. Для каждого теста выведите в одной строке оптимальный маршрут Джони (см. пример для точного формата). Считайте, что такой маршрут всегда существует.

Приклад

Вхідні дані #1
3

Stops: OxfordCircus, PiccadillyCircus, HydeParkCorner, King'sCross, GreenPark, Arsenal, Victoria, Highbury&Islington, LeicesterSquare
Lines: Blue, Cyan
Cyan route: Highbury&Islington, King'sCross, OxfordCircus, GreenPark, Victoria
Blue route: HydeParkCorner, GreenPark, PiccadillyCircus, LeicesterSquare, King'sCross, Arsenal
Johny lives at King'sCross
Michelle lives at GreenPark

Stops: OxfordCircus, PiccadillyCircus, HydeParkCorner, King'sCross, GreenPark, Arsenal, Victoria, Highbury&Islington, LeicesterSquare
Lines: Blue, Cyan
Cyan route: Highbury&Islington, King'sCross, OxfordCircus, GreenPark, Victoria
Blue route: HydeParkCorner, GreenPark, PiccadillyCircus, LeicesterSquare, King'sCross, Arsenal
Johny lives at PiccadillyCircus
Michelle lives at LeicesterSquare

Stops: OxfordCircus, PiccadillyCircus, HydeParkCorner, King'sCross, GreenPark, Arsenal, Victoria, Highbury&Islington, LeicesterSquare
Lines: Blue, Cyan
Cyan route: Highbury&Islington, King'sCross, OxfordCircus, GreenPark, 
...
Вихідні дані #1
optimal travel from King'sCross to GreenPark: 1 line, 3 minutes
optimal travel from PiccadillyCircus to LeicesterSquare: 1 line, 1 minute
optimal travel from Victoria to HydeParkCorner: 2 lines, 7 minutes
Джерело 2013 ACM ICPC Central Europe Regional Contest, Краков, Ноябрь 15-17, Задача D