UOJ Logo

NOI.AC

1S 512MB

#1521. 继续逃

Statistics

继续逃

小明逃出房间后,仍然需要逃出这个楼层。由于火灾现场温度较高,但是房间外面的火并没有蔓延。在一个楼层中有许多出口,只有最远的出口才有机会逃生。请你计算小明逃脱所需要的走的步数。

输入说明

第一行输入n, m。

接下来n行读入m列的字符串。

其中S表示起点,T表示出口,S有且仅有一个,T个数未知。

'#'表示为墙。‘.’表示可以走的路。

可以从一个T到达另外一个T。

对于50%的数据,n,m<=50;

对于100%的数据,n,m<=500;

输出说明

如果小明可以逃脱的话,输出小明需要走的步数。

如果不能逃出的话,输出"IMPOSSIBLE"。

Example

输入:

2 2
ST
TT

输出:

2