题目描述

在中国象棋里，马走动的方法是一直一斜，即先横着或直着走一格，然后再斜向移动一格，俗称 “马走日”。马一次可走的选择点可以达到四周的八个点，故有 “八面威风”之说。如果在要去的方向正前方有别的棋子挡住，马就无法走过去，就是我们所说的 “蹩马腿”

本题是象棋的抽象改编版本，在一个 $n$ 行 $m$ 列的棋盘上，其上共有 $n × m$ 个位置，这些位置上分布着一些棋子，'+' 表示我方的兵，'-' 表示对方的卒，'S' 表示我方的马，'T' 表示对方的将，同时 'T' 也是我方的马行棋终点，特别的是，为了方便输入，'.' 表示该位置无棋子。

为了简化题目，善良的 小 z 召唤了一匹神马 沙琪马，它可以无视蹩马腿的限制~~~😄 😄

接下来介绍一下本题当中的行棋规则。

1. 若马移动一步的位置无棋子，则可以移动。
2. 若马移动一步的位置(马走日)为我方的兵，则不能移动。
3. 若马移动一步的位置(马走日)为对方的卒，则可以移动(马吃卒)。
4. 若马移动一步的位置(马走日)为对方的将，则可以移动(将死)。

现在想让你求出，我方的马最少连续走几步可以到达终点？

#注意本题除了我方的马之外，其余棋子均不动，并且 'S' 和 'T' 的个数都为 $1$ 。

输入格式

第一行包含两个整数 $n,m$ ，$(2≤n,m≤10^3)$，表示棋盘大小。

接下来 $n$ 行 $m$ 列的字符 $c_{i,j}$ ，表示第 $i$ 行第 $j$ 列的位置信息。

输出格式

输出一个整数，表示我方的马最少连续走几步可以到达终点。（数据保证一定可以到达终点）

6 6
.+..+.
......
S.T--+
......
.+..++
......

4

4 5
S++..
+++..
-....
...T.

2

说明/提示