题目背景

学校后山的植物园是一个 $R$ 行 $C$ 列的网格花园，. 是小路、* 是灌木丛（不能走），S 是入口、T 是出口。

小华想从 S 走到 T，每次上下左右走一格，问最少要走几步？

题目描述

求从 S 到 T 的最少步数；若走不到，输出 $-1$。

输入格式

从文件 garden.in 中读入数据。

输入文件 garden.in 共 $R+1$ 行：第一行两个整数 $R, C$；接下来 $R$ 行，每行一个长度为 $C$ 的字符串（由 . * S T 组成）。

输出格式

输出到文件 garden.out 中。

输出文件 garden.out 共一行，一个整数：能到达则是最少步数，不能到达输出 $-1$。

数据范围

对于 $100\%$ 的数据：$1 \le R, C \le 500$，保证 S 和 T 各恰好出现一次（可能重合）。

样例

2 2
S.
.T

2

5 6
.S....
.***.*
.*....
.****.
....T.

9

12 12
S...........
............
............
............
............
......*.....
............
............
............
.....*......
............
...........T

22

样例说明

• 样例 1：$2 \times 2$，S 与 T 相邻。
• 样例 2：$5 \times 6$，存在通路。
• 样例 3：$12 \times 12$，开阔花园。