Каждый год в городе Радон-Снарк проходит всемирно известный симпозиум учёных-космологов.
Профессор 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 г.