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

背景

17陷入了一个魔窟中，他必须要在最短的时间内从起点'S'走到终点'E'。17可以向与他相邻的四个方格中的其中一个前进一步，每走一步都需要花费1时间。特别的是，在这个魔窟中的某个位置有一个陷阱'T'，只有带上保护膜才可以顺利通过，而魔窟中会有一点'P'代表保护膜，只要经过那里就会自动带上。另外，'.'代表魔窟中安全地带，可任意经过，'#'代表墙壁，无法穿过。问17逃出魔窟最少需要多长时间。

输入

第一行有两个正整数m和n，代表魔窟的大小。(2<=m,n<=20)
接下来的m行代表魔窟，每行有n个字符，这些字符只包含'S', 'E', '#', 'T ', 'P', '.'。
其中起点'S'，终点'E'，陷阱'T'，保护膜'P'有且只有一个。

输出

在一行中输出一个整数代表答案，如果无法从起点走到终点，则输出-1。

样例输入

2 10
E.#.S..#.P
..T..#....

样例输出

20