Метро
Метро
Джони собирается навестить своего друга Мишеля. Отец позволил ему это сделать самостоятельно, отправившись на метро. Джони любит ездить на метро и с удовольствием использует эту возможность чтобы провести полдня под землей, однако отец настоял на том чтобы он сменил в метро как можно меньше линий. В городе имеется много станций, а также несколько линий, соединяющих их. Движение всех поездов идеально синхронизировано – время проезда между двумя соседними станциями на каждой линии занимает в точности одну минуту, а смена линий на любой станции происходит мгновенно.
По заданной карте метро помогите Джону так спланировать его поездку, чтобы время путешествия было наибольшим, но при этом в силе оставалось указание отца.
Вхідні дані
Первая строка содержит количество тестов t. Каждый тест имеет следующий формат:
Описание каждого теста начинается с пустой строки. Следующие две строки начинаются фразами Stops: и Lines:, и содержат названия (разделенные запятыми и пробелами) всех остановок метро и линий. Каждая линия метро описывается в одной строке (не важно в каком порядке), начинаясь фразой route: с дальнейшим перечислением станций вдоль линии. Последние две строки задают названия (разных) станций возле домов Джони и Мишеля.
В каждом тесте не более 300000 станций и 100000 линий, общая длина которых не превышает 1000000. Названия станций и линий содержат от 1 до 50 символов - букв, цифр, дефисов (-), апострофов (') и символов "and" (). Все линии двунаправленные (хотя изменение направления движения считается как изменение линии) и без самопересечений.
Вихідні дані
Выведите ответы к тестам в том же порядке в котором они заданы. Для каждого теста выведите в одной строке оптимальный маршрут Джони (см. пример для точного формата). Считайте, что такой маршрут всегда существует.
Приклад
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, ...
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