Leila 是一位高素质医院的外科医生。为了到达手术室，她必须穿过一个候诊大厅，那里有一些患有新冠肺炎症状的病人正在等待检查。为了避免感染，Leila 希望在穿过大厅时与病人保持尽可能大的距离。你的任务是帮助她找到在穿过候诊大厅时，与任何病人之间所能保持的最大距离。

给定一个矩阵形式的大厅地图，其中标记了病人的位置和空座位（她不能穿过这些位置！）。矩阵中两个单元格 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的距离定义为 $\max(|x_1 - x_2|, |y_1 - y_2|)$。座位不会阻挡病毒传播。因此，在定义两个单元格之间的距离时，我们不考虑座位的位置。在每一步中，如果相邻单元格没有座位或病人，Leila 可以从当前单元格移动到大厅中上、下、左、右四个相邻单元格中的任意一个。

输入格式

输入的第一行包含两个整数 $m$ ($1 \leqslant m \leqslant 500$) 和 $n$ ($1 \leqslant n \leqslant 500$)，分别表示行数和列数。接下来 $m$ 行给出了候诊大厅的地图；每一行代表矩阵的一行，包含 $n$ 个字符，“*”表示病人，“#”表示空座位，“.”表示 Leila 可以通过的空闲空间。Leila 的起点用字符“S”表示，路径的终点用字符“E”表示。注意，Leila 在路径中不能走出大厅（即矩阵范围）。

输出格式

输出 Leila 在路径中能与病人保持的最大距离。如果 Leila 根本无法到达手术室，则输出“-1”。否则，如果大厅中没有病人，则输出“safe”。

样例

输入 1

4 5
.*#..
.*..E
..##.
S....

输出 1

2

输入 2

6 8
.......E
........
........
.....**.
........
S.......

输出 2

3

输入 3

3 3
#E#
###
#S#

输出 3

-1

输入 4

3 3
.S.
***
.E.

输出 4

-1

输入 5

3 3
S..
...
..E

输出 5

safe