URI Online Judge | 1799 | [P2][Univ]

The Rat in a Maze

By Neilor Tonin, URI BR Brazil

Timelimit: 1

In 1942, Robert Tryon's study concluded that genetic traits often did, in fact, contribute to behavior, independent of the environment. To do so, Tryon created an experiment that tested the proficiency of successive generations of rats in completing a maze, separating those who made the fewest errors as “bright”, and those with the most errors as “dull”. Continuing this process for seven generations, he created two distinct breeds of “bright” and “dull” rats.

IBO is descendent from the "brilliant" strain of rats, and has the best performance on this experiment. He can come in, pick up the cheese and get out of any maze without getting lost, always making the shortest possible path.

Your task in this problem is, given the design of the labyrinth and the position of the cheese, determine how many points strategically marked by letters or words containing letters of the alphabet IBO must go through to get the cheese (indicated by the character '*') and exit, always starting at the Entrada (word in portuguese that means Entrance) point and ending at the Saida (word in portuguese that means Exit) point. In the example below, the IBO sequence from the Entrada would be: A, F, J, *, I, M, K and Exit, resulting in 8, which is the minimum amount of points in which IBO must go through to do its job. If IBO pass through a point twice (one time going for cheese and one time going to the output) it must count as two points visited.

Input

The first line of input contains two integers Points (4 ≤ Points ≤ 4000) and Links (4 ≤ Links ≤ 5000) representing respectively the number of points strategically marked by letters and the amount of links existing between these points. The following lines indicates all links between the points. The connection between two points indicates that anyone can be the origin.

Output

Print an integer number indicating the minimum amount of points that IBO must go through to do its task.

Input Samples Output Samples

16 20
Entrada A
A F
F C
C B
B D
C D
F J
J H
H G
J G
J *
* I
I L
L M
M K
K Saida
A K
C E
E I
I M

8

10 11
B A
Entrada A
B GO
GO H
H *
B *
* C
C I
I D
C D
D Saida

6