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 RIP ACE.

Input Specification

First line: ~N~, ~T~, the number of destinations, not including home and 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~

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