P1346 Tram

In a magical small town, there is a special tram network composed of intersections and tracks. Each intersection connects to several tracks, and each track leads to an intersection (some scenic tracks may loop back to the same intersection). At every intersection, there is a switch that determines the outgoing track. Each switch has a default position. When a tram arrives at an intersection, it can only leave along the track currently selected by the switch. If the driver wants to take a different track, they must get off and toggle the switch. To reach the destination, drivers often have to get off to toggle switches. Please write a program to compute the minimum number of switch toggles needed for a tram to travel from intersection $A$ to intersection $B$.

The first line contains 3 integers $N, A, B$ ( $2 \leq N \leq 100, 1 \leq A, B \leq N$ ), representing the number of intersections, and the start and destination intersections. Then $N$ lines follow. Each line starts with a number $K_i$ ( $0 \leq K_i \leq N - 1$ ), indicating that this intersection is connected to $K_i$ tracks, followed by $K_i$ integers, each giving the intersection that the corresponding track leads to. The switch’s default position points to the track indicated by the first of these integers.

Output a single integer: the minimum number of switch toggles required to go from $A$ to $B$. If it is impossible to reach $B$ from $A$, output $-1$.

Translated by ChatGPT 5