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

题目背景

\(\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)\)