题目描述

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

树林可以简化为 n 行 m 列的地图，该地图中字符 '.' 表示初始状态下该点没有着火，字符 'F' 表示初始状态下该点着火了，字符 'S' 表示出发点，字符 'T' 表示终点, 字符 '#' 表示障碍物，火不会烧着障碍物，但是人也无法走到走到或者穿越障碍物（火和人都要绕着障碍物走）；当然起点和终点在初始状态下不会着火。

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

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

输入格式

第一行包含两个整数 n , m ( 0 < n, m <= 100 )。

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

输出格式

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

样例

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

6

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

-1