Ace is ready to go to Waterloo for the open house. Unfortunately, his parents won't drive him so he has to take some sort of transit there. Ace always starts at home
and ends up at Waterloo GO
. Along the way, there are RIP ACE
.
Input Specification
First line: home
and Waterloo GO
, and the number of transfers.
Next
Next
Output Specification
The minimum number of transfers to get to Waterloo.
Sample Input 1
2 3
Union Station
MiWay Stop
home-MiWay Stop
MiWay Stop-Union Station
Union Station-Waterloo GO
Sample Output 1
3
Sample Input 2
5 8
China
India
Burma
Uzbekistan
Kyrgyzstan
home-China
China-India
India-Burma
home-Uzbekistan
Uzbekistan-India
Uzbekistan-Kyrgyzstan
Kyrgyzstan-Waterloo GO
Burma-Waterloo GO
Sample Output 2
3
Comments