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 ~N~ ~(1 \le N \le 333)~ stops that Ace can transfer through. Then, there are ~T~ ~(1 \le T \le 999)~ transfers are given in the form ~A~-~B~ where ~A~ is one node and ~B~ is the other. The transfer is two directional, meaning Ace can go from ~A~ to ~B~ or ~B~ to ~A~. The names of the transfers will include a dash. Thus, find the minimum number of transfers for Ace to get to Waterloo for the open house. If Ace cannot, print
First line: ~N~, ~T~, the number of destinations, not including
Waterloo GO, and the number of transfers.
Next ~N~ lines, the name of a transfer.
Next ~T~ lines: a transfer, given in the form ~A~-~B~
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
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