Break a Prison

Jennifer is a software engineer at a tech company. Her company decided to join the ICPC (Inter-Company Prison breaking Contest), and she was chosen as the company's representative.

In the ICPC, every participant must escape from a prison. The prison is an $n \times m$ grid with $n$ rows and $m$ columns of rooms. Room $(i, j)$ is the room in row $i$ and column $j$. Two rooms $(i_1, j_1)$ and $(i_2, j_2)$ are adjacent if and only if $|i_2 - i_1| + |j_2 - j_1| = 1$. There is an unlocked door between every pair of adjacent rooms. Some rooms are under surveillance, and a participant can enter a room only if it is not under surveillance. The starting room and the exit room are guaranteed to be free of surveillance.

The CEO asked Jennifer not to turn right during the contest. That is, there must not be two consecutive moves that satisfy the following condition.

Condition: Suppose Jennifer moves from room $(i_1, j_1)$ to $(i_2, j_2)$ and then to $(i_3, j_3)$. The move is forbidden if $(i_2 - i_1) \times (j_3 - j_2) - (j_2 - j_1) \times (i_3 - i_2) = -1$.

Figure B.1. Example of allowed and denied moves

In Figure B.1, if the last move follows the dashed arrow, Jennifer cannot move downward, but she can move in the other three directions.

U-turns are allowed.

As Jennifer's colleague, write a program that finds the minimum number of moves needed to reach the exit.

The first line contains $n$ and $m$ ($2 \le n, m \le 500$). Each of the next $n$ lines contains $m$ characters. The character $c_{i,j}$ describes room $(i, j)$:

• S: the starting room
• E: the exit room
• .: a room not under surveillance
• #: a room under surveillance

The characters S and E each appear exactly once.

Print the minimum number of moves needed to reach the exit. If the exit cannot be reached, print $-1$.

The optimal route for the third sample is shown below.

Figure B.2. The optimal route in Sample Input 3