감옥 탈출

제니퍼는 IT 기업의 소프트웨어 엔지니어이다. 회사가 ICPC(Inter-Company Prison breaking Contest)에 참가하기로 했고, 제니퍼가 회사 대표로 뽑혔다.

ICPC에서 참가자는 모두 감옥을 탈출해야 한다. 감옥은 $n$행 $m$열의 격자이다. $(i, j)$는 $i$행 $j$열의 방을 뜻한다. 두 방 $(i_1, j_1)$과 $(i_2, j_2)$는 $|i_2 - i_1| + |j_2 - j_1| = 1$일 때만 인접한다. 인접한 방 사이에는 잠기지 않은 문이 하나씩 있다. 일부 방은 감시를 받으며, 참가자는 감시를 받지 않는 방으로만 들어갈 수 있다. 출발 방과 출구 방은 감시를 받지 않는다고 보장된다.

CEO는 대회 중 제니퍼에게 우회전하지 말라고 요청했다. 즉, 연속된 두 번의 이동이 다음 조건을 만족해서는 안 된다.

조건: 제니퍼가 방 $(i_1, j_1)$에서 $(i_2, j_2)$로 이동한 뒤 $(i_3, j_3)$로 이동했다고 하자. 이때 $(i_2 - i_1) \times (j_3 - j_2) - (j_2 - j_1) \times (i_3 - i_2) = -1$이면 그 이동은 금지된다.

그림 B.1. 허용되는 이동과 금지되는 이동의 예

그림 B.1에서 마지막 이동이 점선 화살표 방향이면 제니퍼는 아래로 이동할 수 없고, 나머지 세 방향으로는 이동할 수 있다.

U턴은 허용된다.

제니퍼의 동료로서, 출구에 도달하는 데 필요한 최소 이동 횟수를 구하는 프로그램을 작성하라.

첫 줄에 $n$과 $m$이 주어진다($2 \le n, m \le 500$). 이어지는 $n$개의 줄에는 각각 $m$개의 문자가 주어진다. 문자 $c_{i,j}$는 방 $(i, j)$의 상태를 나타낸다.

• S: 출발 방
• E: 출구 방
• .: 감시를 받지 않는 방
• #: 감시를 받는 방

S와 E는 각각 정확히 한 번씩 나타난다.

출구에 도달하는 데 필요한 최소 이동 횟수를 출력한다. 출구에 도달할 수 없으면 $-1$을 출력한다.

세 번째 입력의 최적 경로는 아래와 같다.

그림 B.2. 입력 3의 최적 경로