Red de Tranvías


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

La red de tranvías de la capital de IslaGrande consiste de un número de intersecciones y líneas conectando algunas de ellas. En cada intersección hay un conmutador (popularmente conocidos como chuchos de ferrocarril) apuntando a una de las líneas que salen de esa intersección. Cuando el tranvía entra en la intersección este puede desplazarse únicamente en la dirección a la que el conmutador está apuntando. Si el conductor del tranvía quiere ir a alguna otra dirección, el manualmente tiene que cambiar el conmutador. Cuando un conductor tiene que conducir de la intersección A hasta la intersección B él trata de elegir la ruta que minimice el número de veces que tendrá que cambiar manualmente los conmutadores.

Escriba un programa que calcule el número mínimo de conmutadores que son necesarias cambiar para viajar de la intersección A hasta la intersección B.

Entrada

La primera línea de la entrada contiene los enteros N, A y B \,(2 \leq N \leq 100, 1 \leq A,B \leq N), separados por un carácter en blanco, donde N es el número de conmutadores en la red, y las intersecciones están numeradas desde 1 hasta N. Cada una de las siguientes N líneas del fichero contienen una secuencia de N enteros separados entre si por un espacio en blanco. El primer número de la i-ésima línea, K, (0 \leq K \leq N-1), representan el número de líneas que salen de la i-ésima intersección. Los próximos K números representan las intersecciones conectadas directamente a la i-ésima intersección. El conmutador en la i-ésima intersección inicialmente está apuntando en la dirección de la primera intersección listada.

Salida

La primera y única línea de la salida debe contener el número mínimo de conmutadores cambiados. Puede ser 0 la respuesta. Si no existe una ruta desde A hasta B se escribirá -1.

Ejemplo de Entrada

3 1 3
1 2
2 1 3
1 2

Ejemplo de Salida

1

Comments

There are no comments at the moment.