题目描述

Gold King 住的小区是长方形的，被划分成一个个格子。Gold King 想从家里去游乐场玩，Gold King 每次可以走到他前后左右四个格子中的其中一个，但不能斜着走，也不能走出街道。部分地区有传送门，传送门可以传到到其他任意一个传送门，从其中一个传送门到另一个传送门需要花费一步。

现在给出地图：

S：代表 Gold King 的家

T：代表游乐场

.：代表道路

X：代表墙壁

G：代表传送门

Gold King 不能穿过墙壁。

输入格式

一行输入 n, m 分别代表城市的长和宽。

接下来 n 行每行 m 个字符，描述城市中的每个格子。

输出格式

如果 Gold King 能到达游乐场，输出走到此处的最短步数，否则输出 -1。

样例组

10 10
XSXXXXXX.X
......X..X
.X.XX.XX.X
.X........
XX.XX.XXXX
....X....X
.XXXXXXX.X
....X.....
.XXXX.XXXG
....X..GTX

18

提示说明

1 ≤ n ≤ 500

1 ≤ m ≤ 500