Congratulation! Under your help Flandre Scarlet passed Level one. Now, she faces a hander Level. Do you want to know it? HaHa! Guess it by yourself~ = =.
Go To Topic,this level goal is walk away from maze in shortest time.
In every second, she could move one block to one of the upper, lower, left and right neighboring blocks. Can the poor doggie survive? Please help him.
Give you a map. You should finish this goal. I think you can help poor Flandre.
The input consists of multiple test cases. The first line of each test case contains two integers N, M ( 2 < N, M < 20 ), The next N lines give the maze layout, with each line containing M characters. A character is one of the following:
'*':an empty block.
'#':a block of wall, which Flandre cannot enter;
'S':the entrance of maze;
'E':the exit of maze;
The input is terminated with two 0's. This test case is not be processed.
For each test case, print in one line "..> <..Thank you very much!!" if the Flandre can survive, or "T_T I want to go out!!" otherwise.
..> <..Thank you very much!!
T_T I want to go out!!