题目描述

给定一个 $n$ 行 $m$ 列的网格迷宫。迷宫由以下字符组成：

• S：起点，保证恰好出现一次。

• E：终点，保证恰好出现一次。

• .：普通空地，你可以花费 1 步 向上下左右四个方向移动到相邻格子（不能移出边界或移到障碍物上）。

• #：障碍物，无法通过。

• > < ^ v：传送带，分别表示向右、左、上、下强制滑行。当你进入传送带格子时，必须沿该方向一直滑动，直到：

  • 到达网格边界（撞墙）
  • 遇到障碍物 #

  整个滑行过程不消耗步数（即花费 0 步）。

求从起点 S 到达终点 E 的最小步数。如果无法到达，输出 -1。

输入格式

第一行两个正整数 $n, m$（$1 \le n, m \le 1000$），表示网格的行数和列数。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，仅包含上述提到的字符，表示迷宫地图。

输出格式

输出一个整数，表示从起点到终点的最小步数。如果无法到达，输出 -1。

样例

样例输入 #1

5 5
S>.v.
####.
.>..E
..###
.....

样例输出 #1

3

样例解释 #1

最优路径如下（坐标从 1 开始）：

注意：$(1,4)$ 是 .（空地），所以传送带在 $(1,3)$ 停止。

样例输入 #2

3 5
S#>vE
#####
.....

样例输出 #2

-1

样例解释 #2

起点 S 被障碍物 # 包围，无法移动到任何其他格子，故无法到达终点。

样例输入 #3

1 20
S>>>>>>>>>>>>>>>>>>E

样例输出 #3

1

样例解释 #3

从 S 进入传送带后，一路滑行直达 E，全程不消耗步数。

数据规模与约定

对于 $100\%$ 的数据，$1 \le n, m \le 1000$。

保证地图中只包含题目描述中提到的字符，且 S 和 E 恰好各出现一次。