e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.

Трамвай

Трамвайная сеть в Загребе состоит из множества перекрестков и рельсов, соединяющих их. На каждом перекрестке имеется переключатель, указывающий на один из рельсов, выходящих из него. Когда трамвай въезжает на перекресток, он может покинуть его только в том направлении, на которое указывает переключатель. Если водитель хочет идти другим путем, он должен вручную изменить переключатель.

Когда водитель едет от перектрестка a к перекрестку b, он старается выбрать путь, на котором количество изменений состояний переключателей минимально.

Напишите программу, которая вычислит наименьшее число изменений фпереключателей, необходимых для проезда от пересечения a до пересечения b.

Входные данные

Первая строка содержит целые числа n, a и b (2n100000, 1a, bn), где n - количество перекрестков в сети, перекрестки пронумерованы числами от 1 до n.

Каждая из следующих n строк содержит последовательность чисел, разделенных пробелом. Первое число в i-ой строке - ki (0kin - 1), указывающее на количество трамвайных путей, исходящих из i-го перекрестка. Следующие ki чисел указывают номера перекрестков, непосредственно связанными с i-ым. Переключатель на i-ом перекрестке изначально указывает на перекресток, который первым указан в списке смежности.

Выходные данные

Вывести наименьшее искомое количество переключений. Если проехать от a до b невозможно, то вывести "-1".

Ліміт часу 1 секунд
Ліміт використання пам'яті 122.17 MiB
Вхідні дані #1
3 2 1
2 2 3
2 3 1
2 1 2
Вихідні дані #1
0
Джерело Croatia OI 2002 Regional - Juniors