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