题目背景

本题满分 $110$。

题目描述

有一块 $n$ 行 $m$ 列的国际象棋棋盘。你要操作皇后（queen）从起点移动到终点。棋盘有如下几种类型的格子：

• $\texttt{S}$：起点。
• $\texttt{E}$：终点。
• $\texttt{\#}$：障碍。
• $\texttt{.}$：空格子。
• $\texttt{1}\sim \texttt{9}$：传送门（见下）。

棋盘上有若干个传送门：$\texttt{1}\sim \texttt{9}$ 中的若干个数字会在棋盘上出现两次。当皇后到达传送门时，可以选择移动到棋盘上另一个写着相同数字的传送门处，这个操作不计入步数。传送之后的第一次移动同样计入步数，无论方向如何。

皇后的移动规则和国际象棋类似：在一步中，可以将皇后移动到同一行，同一列或同一对角线上的任意一个未被障碍物阻挡的格子（换言之，这一步起点到终点连的线段经过的格子不能有障碍物，包括起终点）。

求出从起点到终点的最小步数，或报告无解。

输入格式

第一行，两个正整数 $n,m(1 \leq n,m\leq 1000)$。

接下来 $n$ 行，第 $i$ 行一个长度为 $m$ 的字符串，字符集为 $\{\texttt{S},\texttt{E},\texttt{\#},\texttt{.},\texttt{1}\sim \texttt{9}\}$，其中第 $i$ 行的第 $j$ 个字符 $c_{i,j}$ 表示第 $i$ 行第 $j$ 列的格子类型。

输出格式

若无解，输出一行一个 $\texttt{-1}$。

否则输出一行一个正整数，表示答案。

4 4
S..1
####
1.#E
....

4

3 3
S..
.#.
..E

2

5 4
S.21
####
2##1
###.
E..#

4

提示

样例解释

样例三解释：走到传送门 $1$ 处，传送；然后用三次操作走到终点。可以证明 $4$ 是最少步数。

子任务

• $\text{Subtask 1 (24 pts)}$：$n,m\le 5$。
• $\text{Subtask 2 (32 pts)}$：无传送门。
• $\text{Subtask 3 (18 pts)}$：$n,m\le 500$。
• $\text{Subtask 4 (36 pts)}$：无额外限制。