题目描述

小z 指派你执行一项星际探险任务，任务当中你的飞船需要穿越一个由多个星系组成的复杂迷宫，以到达遥远的目标星系。这个迷宫由 n 行 m 列的星系组成，每个星系相当于迷宫中的一个格子。

在这片浩瀚的星际空间中，某些星系因黑洞、星际尘埃等危险因素而不适宜飞船穿越，这些星系被标记为障碍物 '#'，你的飞船无法通过。然而，其他星系是安全的 '.' ，允许飞船在其之间进行四方向移动一个方格 (上、下、左、右)，每次移动将耗费一秒钟的时间。

此外，迷宫中散布着一些特殊的星系，它们用小写字母 ('a'~'z') 来表示。当你的飞船抵达这些星系时，除了四方向移动之外，还可以利用一种特殊的星际传送技术，传送到迷宫中任意一个含有相同字母的星系，每次传送同样耗费一秒钟。

你的主要任务是设计一条从起点星系（标记为 'S'）到终点星系（标记为 'T'）的最优航线，问所需最少时间是多少？

题目保证可以到达终点。

输入格式

第一行包含两个整数 $n,m$ ，表示迷宫的大小。

接下来 $n$ 行 $m$ 列的字符 $c_{i,j}$ ，表示第 $i$ 行第 $j$ 列位置方格的信息。

输出格式

一行一个整数，输出到达终点所需最少时间。

4 5
S....
..#a#
...#a
.#..T

6

提示

【数据范围】

对于 $60\%$ 的数据：$1≤n,m≤10$。

对于 $100\%$ 的数据保证：$1≤n,m≤10^3$。