A137132.传送门迷宫

$Sherry$ 进入了一座带有传送门的迷宫。迷宫可以看成一个 $n$ 行 $m$ 列的字符矩阵。

每个格子可能是以下几种字符：

• S 表示起点；
• T 表示终点；
• . 表示空地；
• # 表示墙，不能进入；
• 小写字母 a 到 z 表示传送门。

$Sherry$ 每一步可以选择以下一种操作：

• 向上、下、左、右移动一格，移动到相邻的非墙格子；
• 如果当前位置是某个小写字母 $c$，可以花费 $1$ 步传送到任意另一个同样为 $c$ 的格子。

传送门不会因为使用而消失。请你求出从起点 S 到终点 T 至少需要多少步。如果无法到达，输出 $-1$。

第一行输入两个整数 $n,m$，表示迷宫的行数和列数。

接下来 $n$ 行，每行输入一个长度为 $m$ 的字符串，表示迷宫。

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

数据范围

$1\le n,m\le 1000$

$n\times m\le 10^6$

保证迷宫中恰好有一个 S 和一个 T。