catleap

Problem Description

Rar the Cat found himself in a H by W cells park with either blank spaces or obstacles, denoted by '.' or '#' respectively.

Rar the Cat starts at the position denoted as 'S' and wants to get to the position denoted by 'E'. He wants to know the shortest time (in minutes) that it takes to get there..

Rar the Cat can traverse from one blank space to another adjacent blank space to its left, right, up or down by walking. This takes 1 minute.

However, if there is a obstacle in front of Rar the Cat, Rar the Cat can jump onto the obstacle and leap across it. This also takes 1 minute. This only applies if there is a blank space at the opposite end of the obstacle.

Refer to the park layout below, where the position of Rar the Cat is denoted as 'R':

.....
..#..
..#..
..R#.
.#.#.

Rar the Cat can walk from its current position, to either of the two blank spaces denoted by '*' below:

.....
..#..
..#..
.*R#.
.#*#.

In addition, Rar the Cat can leap across the obstacle on the right, reaching the position denoted by '*' below:

.....
..#..
..#..
..R#*
.#.#.

However, Rar the Cat cannot leap upwards as there is 2 cells of obstacles. Rar the Cat can only leap across 1 cell of obstacles. In addition, Rar the Cat cannot leap to its left as well, as there is no obstacle to its left.

Limits

For all testcases, 0 < Sx, Ex ≤ H, 0 < Sy, Ey ≤ W.

Subtask 1 (39%): H = 1, 1 ≤ W ≤ 1024.

Subtask 2 (12%): 1 ≤ H, W ≤ 1024. In addition, there will be no obstacles.

Subtask 3 (49%): 1 ≤ H, W ≤ 1024.

Subtask 4 (0%): Sample Testcases.

Input

The first line of input will contain two integers, H, W..

There will be H lines containing W characters each. Each character will either be '.', '#', 'S' or 'E', representing a blank space, an obstacle or the starting and ending locations respectively. 'S' and 'E' will only appear once in the input.

Output

The output should contain a single integer, the minimum amount of time Rar the Cat needs to get from the starting location to the ending location in minutes. If it is not possible for Rar the Cat to get from the starting position to the ending position, print '-1' instead.

Sample Testcase 1

Input

1 10
S..#.#..#E

Output

6

Explanation

Rar the Cat walks right for 2 minutes, then leaps over one obstacles for two times. He then walks for 1 minute to the right, and leaps over an obstacle again to reach the final destination.

Sample Testcase 2

Input

3 20
.#.#.#.#.#..........
S..................E
..........#.#.#.#.#.

Output

14

Explanation

Rar the Cat takes the following route denoted by '*':

*#*#*#*#*#..........
S.......**.........E
.........*#*#*#*#*#*

Sample Testcase 3

Input

3 3
S#.
#E#
.#.

Output

-1

Explanation

Rar the Cat can reach every other blank space except the ending point.