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

Чемпионат Урала 2005 Тур II

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

B. Космология против Хронологии

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Каждый год в городе Радон-Снарк проходит всемирно известный симпозиум учёных-космологов.
Профессор A, завсегдатай симпозиума, решил пригласить на этот раз в гости профессора B, занимающегося в смежной области — прикладной хронологии.
Пригласить — пригласил, а вот встретить его на вокзале забыл (задумался о прекрасном будущем космологии, а о приезде друга вспомнил лишь в тот момент, когда B уже прибыл в город). "Делать нечего — надо ехать", — решил A, сел в свой космомобиль и отправился в путь.
Учёный с мировым именем B не зря занимался хронологией. Сейчас он просто не мог ждать ни секунды (ведь в отличие от космологов хронологи считают, что действия, а не какие-то там туманные рассуждения являются истинно верными), поэтому сел в свой хрономобиль и отправился на встречу. Осталось выяснить, когда профессор A встретит учёного с мировым именем B, чтобы суметь привлечь его к космологии.
Но не забудьте учесть, что вот-вот начнётся симпозиум, а с ним всегда были связаны странные явления. Во время дискуссий именитых учёных вся техника в городе ведёт себя причудливым образом. Так, уже сейчас все космомобили на любом перекрёстке поворачивают в самый левый свороток, а хрономобили — в самый правый. Выходить из транспортного средства между двумя перекрёстками в Радон-Снарке противозаконно, поэтому профессора A и B могу встретиться только на перекрёстке.

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

В первой строке находится одно число N (N ≤ 100000) — количество перекрёстков в Радон-Снарке. Далее следуют N строк, описывающих перекрёстки. (i + 1)-я строка содержит список перекрёстков, достижимых непосредственно c i-го перекрёстка. Дороги в списке перечисляются слева направо. Все дороги начинаются с одной и той же стороны перекрёстка, поэтому понятия "самый левый" и "самый правый" имеют смысл. Список заканчивается нулём. Любой список содержит как минимум одно ненулевое число. Перекрёсток может быть связан дорогой с самим собой.
В последней строке записаны два числа. Первое — перекрёсток, путешествие с которого начинает A, второе — аналогичный перекрёсток для B.

Результат

Выведите время в минутах, через которое B встретит A и сможет показать ему, что лучшее занятие, которым может заниматься человек в наше высокотехнологичное время — это хронология. И хрономобиль, и космомобиль проезжают дорогу, связывающую два перекрёстка, ровно за одну минуту. Выведите −1, если эта знаменательная встреча никогда не состоится.

Пример

исходные данныерезультат
7
2 4 0
3 1 0
4 2 0
5 1 6 3 0
6 4 0
2 5 4 0
6 0
1 7
7
Автор задачи: Евгений Крохалев (идея — Александр Клепинин)
Источник задачи: IX Чемпионат Урала по спортивному программированию. Екатеринбург, УрГУ, 19-24 апреля 2005 г.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1361. Космология против Хронологии