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

在 ICPC 中，每位参赛者都需要从监狱中逃脱。监狱可以表示为一个 $n \times m$ 的网格：它有 $n$ 行 $m$ 列房间。行从 1（顶部）到 $n$（底部）编号，列从 1（左侧）到 $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) \cdot (j_3 - j_2) - (j_2 - j_1) \cdot (i_3 - i_2)$ 的结果不得等于 $-1$。

例如，在上图中，如果最后一次移动是沿着虚线箭头方向，Jennifer 不能向下移动，但她可以在其他三个方向上移动。

注意，在此条件下允许掉头（180 度转弯）。

作为 Jennifer 的同事，你需要帮助她！编写一个程序，为她找到到达出口所需的最少移动步数。

输入格式

第一行包含两个整数 $n$ 和 $m$：监狱的行数和列数（$2 \le n, m \le 500$）。

接下来 $n$ 行，每行包含恰好 $m$ 个字符。字符 $c_{i,j}$（其中 $1 \le i \le n$ 和 $1 \le j \le m$）描述了第 $i$ 行第 $j$ 列房间的状态。它可以是以下字符之一：

• ‘S’ 表示参赛者的起始房间，
• ‘E’ 表示出口所在的房间，
• ‘.’ 表示普通房间（未受监视），
• ‘#’ 表示处于监视下的房间。

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

输出格式

输出 Jennifer 到达出口所需的最少移动步数。如果她无法在遵守所有规则的情况下到达出口，则输出 $-1$。

样例

输入 1

2 4
S..#
..E.

输出 1

3

输入 2

2 4
S..#
##E.

输出 2

-1

输入 3

2 4
S...
##E.

输出 3

5

说明

样例 3 的最优路径之一：