时间限制：1000ms　内存限制：512MB

题目描述

程老师有一个巨大的仓库，仓库被划分为 $n$ 行 $m$ 列的网格。每个格子可能是以下几种之一：

• 普通地面（用 . 表示）：机器人可以正常行走；
• 货架（用 # 表示）：不可进入的障碍物；
• 冰面（用 * 表示）：特殊的光滑地面；
• 起点（用 S 表示）：机器人的出发位置，恰好一个；
• 终点（用 T 表示）：货物的目的地，恰好一个。

仓库里的搬运机器人遵循以下移动规则：

1. 在普通地面（或 S/T）上，每一步可以向上下左右四个方向之一移动到相邻的非货架格子，消耗 1 次动作。

2. 踏上冰面后的滑行规则：当机器人从非冰面格子踏入冰面格子时，会沿着进入的方向一直滑行——穿过所有连续的冰面格，直到遇到以下情况之一才停下：

   • 前方是货架（#）：停在最后一格冰面上；
   • 前方是仓库边界：停在最后一格冰面上；
   • 前方是非冰面格（普通地面、S 或 T）：停在那个非冰面格上。

   整个滑行过程只计 1 次动作。

3. 如果机器人已经停在冰面上，它可以继续选择四个方向之一移动，同样遵循上述滑行规则。

现在给出仓库的地图，请你帮助程老师计算搬运机器人从起点 $S$ 到终点 $T$ 的最少动作次数。如果无法到达，输出 $-1$。

输入格式

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

第一行两个正整数 $n, m$，表示仓库的行数和列数。

接下来 $n$ 行，每行 $m$ 个字符，表示仓库地图。每个字符只可能是 .、#、*、S、T 之一。地图中恰好有一个 S 和一个 T。

输出格式

输出到文件 ice.out 中。

输出一个整数，表示从 $S$ 到 $T$ 的最少动作次数。如果无法到达，输出 $-1$。

样例

样例 1

输入：

3 3
S.*
*..
T..

输出：

1

样例 2

输入：

2 4
S.*#
T...

输出：

1

样例 3

输入：

2 2
S#
#T

输出：

-1

样例 1 解释

机器人从 S（第 1 行第 1 列）向下踏入第 2 行第 1 列的冰面，沿下方滑行；再往下第 3 行第 1 列是 T（非冰面），停在 T 上。整个过程只计 1 次动作。

数据范围

对于所有测试数据，$1 \le n, m \le 500$，地图中恰好有一个 S 和一个 T。

• 特殊性质 A：没有冰面（地图中只有 .、#、S、T）。
• 特殊性质 B：冰面只出现在单独一整行（存在某一行整行都是 *，其余行没有冰面）。