eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Трамвай

Трамвай

Трамвайная сеть в Загребе состоит из множества перекрестков и рельсов, соединяющих их. На каждом перекрестке имеется переключатель, указывающий на один из рельсов, выходящих из него. Когда трамвай въезжает на перекресток, он может покинуть его только в том направлении, на которое указывает переключатель. Если водитель хочет идти другим путем, он должен вручную изменить переключатель. Когда водитель едет от перекрестка $a$ к перекрестку $b$, он старается выбрать путь, на котором количество изменений состояний переключателей минимально. Напишите программу, которая вычислит наименьшее число изменений переключателей, необходимых для проезда от пересечения $a$ до пересечения $b$. \InputFile Первая строка содержит целые числа $n, a$ и $b~(2 \le n \le 10^5, 1 \le a, b \le n)$, где $n$ --- количество перекрестков в сети, перекрестки пронумерованы числами от $1$ до $n$. Каждая из следующих $n$ строк содержит последовательность чисел, разделенных пробелом. Первое число в $i$-ой строке $k_i~(0 \le k_i \le n - 1)$, указывающее на количество трамвайных путей, исходящих из $i$-го перекрестка. Следующие $k_i$ чисел указывают номера перекрестков, непосредственно связанными с $i$-ым. Переключатель на $i$-ом перекрестке изначально указывает на перекресток, который первым указан в списке смежности. \OutputFile Выведите наименьшее искомое количество переключений. Если проехать от $a$ до $b$ невозможно, то выведите $-1$. \includegraphics{https://static.e-olymp.com/content/e6/e6c88e7f727365c39ca6a89b1503b43dc905b3c3.gif}
Лимит времени 1 секунда
Лимит использования памяти 122.17 MiB
Входные данные #1
3 2 1
2 2 3
2 3 1
2 1 2
Выходные данные #1
0
Источник Croatia OI 2002 Regional - Juniors