Problem C: PIPI的生化危机

Problem C: PIPI的生化危机

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 715  Solved: 114
[Submit] [Status] [Web Board] [Creator:]

Description

浣熊市爆发了生化危机,PIPI作为上班迟到的一名新警察,被困在警察局了,他希望能从警察局前往安全屋避难。
已知浣熊市是个n*m的区域,每块格子的类型有以下几种:
*:表示第0秒时该地点有病毒,且每过1秒病毒就会往上/下/左/右四个方向扩散一格,被病毒新侵占的格子又会按照此规则继续扩散。
S:表示警察局,也就是PIPI一开始所在的地方。
T:表示安全屋,任何病毒都不能扩散到安全屋,这也是PIPI要到达的地方。
#:表示该地点已被摧毁,病毒无法扩散到该地点,同时PIPI也无法移动到该地点。
.: 表示空地。
以上类型中,如无特别说明的,均能被病毒扩散到。 
PIPI每秒可以往上/下/左/右四个方向移动一格,由于PIPI希望能在警察局搜集到足够多的物资,所以他想保证自己在逃亡之旅上不会被病毒感染的情况下,尽可能的在警察局待得久。
请问PIPI在警察局最多能待多少秒?

Input

第一行输入两个整数n,m,其中:2<=n,m<=1000。
接下来n行,每行m个字符,描述浣熊市的情况,保证只有一个警察局和一个安全屋,且PIPI能待在警察局的时间不为无限大。

Output

输出PIPI在警察局最多能待多少秒,若PIPI无法逃离到安全屋,输出-1。

Sample Input

3 3
S.T
...
*..

Sample Output

1