Трамвай
Трамвай
Трамвайная сеть в Загребе состоит из множества перекрестков и рельсов, соединяющих их. На каждом перекрестке имеется переключатель, указывающий на один из рельсов, выходящих из него. Когда трамвай въезжает на перекресток, он может покинуть его только в том направлении, на которое указывает переключатель. Если водитель хочет идти другим путем, он должен вручную изменить переключатель.
Когда водитель едет от перекрестка a к перекрестку b, он старается выбрать путь, на котором количество изменений состояний переключателей минимально.
Напишите программу, которая вычислит наименьшее число изменений переключателей, необходимых для проезда от пересечения a до пересечения b.
Вхідні дані
Первая строка содержит целые числа 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-ом перекрестке изначально указывает на перекресток, который первым указан в списке смежности.
Вихідні дані
Выведите наименьшее искомое количество переключений. Если проехать от a до b невозможно, то выведите -1.
Приклад
3 2 1 2 2 3 2 3 1 2 1 2
0