题目描述

在一片树林中，发生了几处火灾，A小队接到了一个紧急任务，要从 $S$ 点出发到 $T$ 点，去保护 $T$ 点的重要物资。

树林可以简化为 $n$ 行 $m$ 列的地图，该地图中字符 . 表示初始状态下该点没有着火，字符 F 表示初始状态下该点着火了，字符 S 表示出发点，字符 T 表示终点；当然起点和终点在初始状态下不会着火。

A小队每秒钟可以向上下左右四方向移动 $1$ 步，着火的点每秒会蔓延到相邻的 $8$ 个方向的位置，在任何时刻，A小队都无法移动到已经着火的位置上。

请问：A小队从 $S$ 点出发，最短需要多久能到达 $T$ 点，如果无论如何都无法到达 $T$ 点，请输出 $-1$ 。

输入

第一行包含两个整数 $n,m$ （ $0 \lt n, m \le 100$ ）。

接下来 $n$ 行给出一个字符矩阵，矩阵中字符的含义如题所述。

输出

请输出从出发点到终点的最短时间是多少秒，如果无法到达终点，请输出 $-1$ 。

样例

8 10
..........
.F........
..........
..........
..........
....S.....
.........T
..........

6

6 10
..........
..........
.S........
..........
.........T
...FF.....

-1