题目描述

一天 33DAI 在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由 $n\times m$ 的格点组成，每个格点只有4种状态，S、E、. 和 #，分别表示起点、终点、道路、围墙。

33DAI 现在在 S 的位置，他希望走到 E 的位置，他的移动方式有一些限制：

• 正常每次可以走到上下左右相邻的道路中。
• 如果已经连续在某个方向走了三步了，那么下一步就不能往那个方向了。
  • 提示：这个时候你可以回头走一步再继续往前，或者往另外两个方向走。

请问 33DAI 最少几步可以从 S 走到E。如果无论如何都无法到达，输出 -1。

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，每行由 $m$ 个字符构成。即 $n\times m$ 的格点。

输出格式

一个数，即最少次数。

1 6
S....E

7

样例 1 解释

只能：右右右左右右右

3 6
.#S...
.####.
...E#.

-1

5 18
S................E
.################.
.################.
..##....##....##..
#....##....##....#

29

样例 3 解释

往右走不如从下面走

数据规模与约定

对于 $100\%$ 的数据，$1 \le n,m \le 10^5$ 且 $n\times m\le 10^5$。

• 子任务 1（30 分）：保证 $n = 1$。
• 子任务 2（30 分）：保证没有围墙。
• 子任务 3（40 分）：没有特殊限制。