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