该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

$\rm jyh$ 在玩 $\rm Minecraft$ 时不小心走进了一个矿洞里，走了很久他迷路了，他想请你帮帮他走出这个矿洞。

题目描述

我们假设这个矿洞是一个 $\ N × M$ 的二维平面。

• 你可以经过平地。平地用 "." 表示。

• 在这个矿洞里很多岩石阻挡你的去路，凡是有岩石的地方你都不能经过。岩石用 "#" 表示。

• 矿洞里还有许多钻石。假设你有无限根木棍，并且仅需 $1$ 颗钻石就可以制作一把钻石镐。钻石用 "*" 表示。

• 如果你拥有钻石镐，你可以选择挖掉 $1$ 颗上、下、左、右的岩石，当你用过钻石镐后，这把钻石镐就废掉了（不要问我为什么）。

• 你可以装载无限个钻石镐

起点用 "T" 表示，终点用 "S" 表示， 求走的最小步数。

如果走不出矿洞则输出 $-1$

输入格式

第一行: 两个整数 $N, M$

接下来 $N$ 行，每行 $M$ 个整数

输出格式

一个整数，表示最小步数

样例组

样例输入1

4 5
T.##S
..#..
*.###
..*..

样例输出1

8

样例输入2

4 5
T###S
..###
*.###
..*.#

样例输出2

-1

提示说明

对于 $100\%$ 的数据：$N, M ≤ 50$

数据保证钻石数量小于 $1000$

对于 样例一 的解释：

我们可以走以下路径取得最小步数 $8$

$(1, 1) → (2, 1) → (3, 1) → (3, 2) → (2, 2) → (2, 3) → (2, 4) → (2, 5) → (1, 5)$