ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1575. Екатеринбургское метро 2

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Как вы знаете, в Екатеринбурге всего одна линия метро. Каждая станция нашего метрополитена — настоящий архитектурный шедевр. Впрочем, это не очень-то радует жителей Екатеринбурга, которым приходится каждый день утром ехать из дома на работу или на учёбу, а вечером — назад. В любом районе Екатеринбурга в любое время суток огромные пробки, поэтому, конечно, все жители мечтают о том, чтобы рядом с их домом и работой как можно скорее были бы построены новые станции метро.
Мэрия Екатеринбурга решила учесть пожелания горожан. На совещании у Главы города был принят Стратегический план развития метро в Екатеринбурге на срок до 2523 года. Планируется, что к 800-летию Екатеринбурга метрополитен будет состоять из 70 станций!
Вам, неизвестно каким образом, попалась в руки схема Екатеринбургского метро 2523 года (см. рисунок). На схеме 70 станций, формирующих 8 линий; многие станции являются пересадочными. На пересадочных станциях может пересекаться от 2 до 4 различных линий метро. Вам стало интересно, сколько времени потребуется, чтобы добраться от одной станции до другой. Известно, что метропоезда будущего смогут преодолевать любой перегон Екатеринбургского метро ровно за 1 минуту. Кроме того, пересадку с любой линии на любую на пересадочной станции можно считать мгновенной (Вам ведь не нужно внимательно осматривать станции, в отличие от туристов, которые будут приезжать в Екатеринбург только для того, чтобы полюбоваться красотами нашего метро). Временем ожидания поезда также следует пренебречь.
Problem illustration

Исходные данные

В первой строке находится целое число N — количество тестов (1 ≤ N ≤ 4900). Далее в N строках перечислены тесты. Каждый тест состоит из названий 2-х станций, разделённых ровно одним пробелом. Названия могут содержать маленькие и большие латинские буквы, а также символы подчёркивания. Названия всех станций, кроме «Prospekt_Kosmonavtov» и «Kamennye_palatki», приведены на схеме метро точно так же, как они будут представлены на вводе.

Результат

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

Пример

исходные данныерезультат
6
Prospekt_Kosmonavtov Geologicheskaya
Shevchenko Vilonovskaya
Koltsovo Zelyony_ostrov
Teatralnaya Kamennye_palatki
China_town Italyanskaya
1905_year_square 1905_year_square
6
3
11
3
9
0
Автор задачи: Александр Ипатов
Источник задачи: XIV Открытое командное первенство школьников Свердловской области по программированию