说明

Jennifer 是一家科技公司的软件工程师。她的公司决定参加 ICPC（公司间越狱竞赛），她被选为公司的代表。

在 ICPC 中，每位参与者都需要从一个监狱中逃脱。该监狱可以表示为一个 $n \times m$ 的网格，即它有 $n$ 行和 $m$ 列的房间。监狱中第 $i$ 行第 $j$ 列的房间记为房间 $(i, j)$。

两个房间 $(i_1, j_1)$ 和 $(i_2, j_2)$ 相邻，当且仅当 $|i_2 - i_1| + |j_2 - j_1| = 1$。奇怪的是，每对相邻房间之间都有一扇未上锁的门。监狱中的一些房间处于监控之下。参与者只能移动到未被监控的房间。参与者将从某个房间出发。所有参与者的目标是到达一个出口。保证带有出口的房间和参与者出发的房间未被监控。

为了展示公司的才华，CEO 要求 Jennifer 在比赛中不要右转。换句话说，在房间之间的移动中，不得出现任何两次连续的移动满足以下条件：

条件：假设 Jennifer 从房间 $(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$ 成立。

:::align{center}

图 B.1. 允许和禁止移动的示例 :::

例如，在图 B.1 中，如果上一次移动是沿着虚线箭头方向，则你不能向下移动，但可以向其他三个方向移动。

注意，在此条件下，掉头（U 形转弯）是允许的。

作为 Jennifer 的同事，你的任务是编写一个程序，为她找到到达出口所需的最少房间间移动次数。

输入格式

输入包含一个单独的测试用例，格式如下：

$$\begin{aligned} &n \ m \\ &c_{1,1} c_{1,2} \ldots c_{1,m} \\ &c_{2,1} c_{2,2} \ldots c_{2,m} \\ &\vdots \\ &c_{n,1} c_{n,2} \ldots c_{n,m} \end{aligned}$$

$n$ 和 $m$ 表示监狱的大小，每个都是介于 $2$ 到 $500$ 之间的整数。$c_{i,j}$（$1 \leq i \leq n$，$1 \leq j \leq m$）是一个描述第 $i$ 行第 $j$ 列房间状态的字符。该字符可能是：

• 'S'：表示参与者的起始房间，
• 'E'：表示带有出口的房间，
• '.'：表示该房间未被监控，或
• '#'：表示该房间处于监控之下。

保证输入中 'S' 和 'E' 各恰好出现一次。

输出格式

输出 Jennifer 到达出口所需的最少房间间移动次数。如果她无法到达出口，输出 $-1$。

2 4
S..#
..E.

3

2 4
S..#
##E.

-1

2 4
S...
##E.

5

提示

在样例输入 3 中，其中一条最优路线如下：

:::align{center}

图 B.2. 样例输入 3 中的最优路线 :::

翻译由 DeepSeek V3.2 完成