Warehouse Robot

Story

A delivery robot starts at the loading dock S of a warehouse and must reach the exit E. Shelving units (#) block the way; the free floor (.) is where it can drive. The operator wants to know the shortest route, and whether a route exists at all.

Task

On a grid the robot moves one cell at a time up, down, left or right (no diagonals), never onto a # cell and never off the grid. Print the minimum number of moves from S to E, or -1 if E cannot be reached.

Input

• Line 1: R C, the number of rows and columns
• Then R lines of exactly C characters: . free, # wall, S start, E exit

There is exactly one S and one E. Limits: 1 ≤ R, C ≤ 200 (up to 40 000 cells), so trying every possible path is hopeless.

Output

One integer: the minimum number of moves, or -1.

Example

5 8
S..#....
.#.#.##.
.#...#..
.####.#.
......#E

Output: 15. The shelves force a long detour along the top and down the right-hand side.

5 8
S..#....
.#.#.##.
.#...#..
.####.#.
......#E