Minimum Subway Transfers

In a sprawling metropolitan subway system, each subway line serves a sequence of stations. When traveling from a starting station to a destination station, passengers may need to change lines (transfer) at stations where multiple lines intersect. However, if both the starting and destination stations are on the same line, no transfer is required.

Your task is to compute the minimum number of transfers required to travel between two given stations. If the journey is impossible, output -1.

Note: The initial boarding does not count as a transfer. Transfers only occur when you switch from one subway line to another.

The subway system is described by an integer L which represents the number of subway lines. This is followed by L lines; each line lists the station names (separated by spaces) served by that subway line. Finally, the last line of input contains the starting station followed by the destination station.

The answer should be output as a single integer representing the minimum number of transfers required.

inputFormat

The input begins with an integer L (the number of subway lines). Following this are L lines, each containing the names of the stations on that subway line separated by spaces. The final line contains two station names separated by a space: the starting station and the destination station.

outputFormat

Output a single integer representing the minimum number of transfers required from the starting station to the destination station. If it is not possible to reach the destination, output -1.

3
S1 S2 S3 S4 S5 S6 S7
A S4 S8 S9 B
C D S5 G H
S1 S9

1