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

小明要回家，但是他家的钥匙在他的朋友小红手里，他要先从小红手里取得钥匙才能回到家。小红告诉他：“你家的钥匙被我复制了很多个，分别放在不同的地方。”

小明希望能尽快回到家中，他首先需要取得任意一把钥匙，请你帮他计算出回家所需要的最短路程。

小明生活的城市可以看做是一个 $n×m$ 的网格，其中有道路有障碍，钥匙和家所在的地方可以看做是道路，可以通过。小明可以在城市中沿着上下左右 $4$ 个方向移动，移动一个格子算做走一步。

输入格式

第一行有两个整数 $n$，$m$。城市的地图是 $n$ 行 $m$ 列。$(1≤n,m≤2000)$

接下来的 $n$ 行，每行 $m$ 个字符，代表城市的地图。'.'代表道路，'#'代表障碍物，'S'代表小明所在的位置，'T'代表小明家的位置，'P'代表钥匙的位置。除了障碍物以外，别的地方都可以通过。题目保证小明至少有一条路径可以顺利拿到钥匙并且回家。

输出格式

输出小明回家要走的最少步数，占一行。

格式说明输出时每行末尾的多余空格，不影响答案正确性

输入、输出要求要求使用「文件输入、输出」的方式解题，输入文件为 home.in，输出文件为 home.out

样例输入

8 10
P.####.#P#
..#..#...#
..#T##.#.#
..........
..##.#####
..........
#####...##
###....S##

样例输出

21