Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

EIDIS221222FQ2 - EIUCOUNTROOM

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

Output

5 8

########

#.A#...#

#.##.#B#

#......#

########

YES

9


Added by:Ha Minh Ngoc
Date:2022-03-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.