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