Given a map which is described by characters . (floor), # (wall), S (start), or E (end). You can walk left, right, up and down on the floor (dot character). Write a program to find a path from start to end.

Input

• The first line has two integers ~n~ and ~m~, the height and width of the map ~(1 ≤ n, m ≤ 1000)~
• The next ~n~ lines are the map. There is one start and end point in the map.

Output

• If there is a path, then print the length of the shortest path. If there is no path, print -1

Sample Input

5 8
########
#.A#...#
#.##.#B#
#......#
########

Sample Output

YES
9