U715791 JY 的头疼光环 (JY's Headache Aura)

期末复习周到了，JY 决定去学校最大、最像迷宫的地下图书馆自习。 但是，JY 是一个极度偏科、一看到数学题就会头疼的同学。不幸的是，此时正值考研大军复习《高等数学》和《离散数学》的高峰期，图书馆的许多书桌上都放着厚厚的数学书。 对 JY 来说，这些数学书就像是核废料一样，会向四周散发出可怕的“头疼光环”。距离某本数学书越近，JY 感受到的“头疼指数”就越高；距离越远，他就越有安全感。

图书馆可以看作是一个 $N \times M$ 的网格地图。 地图中的每个格子可能是以下几种情况之一： - `.`：空地，可以自由通行。 - `#`：书架或墙壁等障碍物，无法通行。 - `M`：放着数学书的桌子（数学书辐射源），JY **不能**走到这些格子上。 - `S`：JY 的当前位置（起点）。 - `E`：JY 想要到达的安全自习室（终点）。 我们定义某个空地格子的**“安全指数”**为：该格子到**离它最近的**一个数学书 (`M`) 的**曼哈顿距离**。 （注：网格中两点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的曼哈顿距离为 $|x_1 - x_2| + |y_1 - y_2|$）。 JY 想从起点 `S` 走到终点 `E`（每次只能上下左右移动一步，不能穿过障碍物和数学书）。 在走过的这条路线上，必然会有一个格子离数学书最近（即安全指数最小，头疼指数最高）。JY 希望规划出一条完美的路线，使得这条路线上所有格子中**最小的“安全指数”尽可能大**（也就是离数学书最远）。 因为 JY 对于数学与关于数学的信竞题一窍不通，所以他请你帮忙计算出，所有可行路线中，最大的“最小安全指数”是多少？ 如果他无论如何都无法从 `S` 走到 `E`，请输出 `-1`。

第一行包含两个整数 $N, M$，表示图书馆网格的行数和列数。 接下来 $N$ 行，每行包含一个长度为 $M$ 的字符串，代表图书馆的地图。 保证地图中恰好有一个 `S`，恰好有一个 `E`，并且**至少有一个 `M`**。

输出一个整数，表示路线中最大的“最小安全指数”。如果无法到达，输出 `-1`。

**【样例解释 1】** 有两个数学书 `M`，分别在 $(0, 4)$ 和 $(4, 0)$。 最优路线之一是：`(0,0) -> (1,0) -> (1,1) -> (1,2) -> (2,2) -> (3,2) -> (4,2) -> (4,3) -> (4,4)`。 在这条路线中，距离数学书最近的格子是起点 $(0,0)$ 和终点 $(4,4)$ 以及中间的 $(2,2)$ 等，它们到最近的 `M` 的曼哈顿距离为 4（例如 (0,0) 到 (4,0) 距离为 4）。 但是等等，路线如果往右走，比如经过 $(0,1)$，它到 $(0,4)$ 的距离只有 3。 实际上，最优路径在中间穿插，所有经过的格子中，到最近的 `M` 的最小距离（安全指数）最大能保持在 $2$。 **【样例解释 2】** 被墙壁完全堵死，无法到达，输出 `-1`。 ### 数据规模与约定 - 对于 $30\%$ 的数据，$1 \le N, M \le 50$。 - 对于 $100\%$ 的数据，$1 \le N, M \le 1000$。地图仅由 `.`, `#`, `M`, `S`, `E` 组成。