Maze Vision

Harry has an extraordinary vision. From one end of the maze he can see the other end along a straight line in one of the eight directions (north, northeast, east, southeast, south, southwest, west, and northwest). However, the maze is opaque; walls block his view. Harry runs very fast, taking only $1\text{s}$ per step when moving up, down, left, or right by one cell. Since burning down the maze walls is not an option, Harry chooses to go around until he can see the trophy. Your task is to help him determine the minimum time required to get to the trophy.

The maze is represented by a grid with n rows and m columns. Each cell is either:

• S - Harry's starting position
• T - The trophy
• # - A wall
• . - An open space

Harry can move in the four cardinal directions (up, down, left, right) with each move taking 1 second. At any cell, Harry can see the trophy if it lies exactly in one of the eight directions (including diagonals) and there is no wall in between. If the trophy is already visible from his current cell, he can grab it immediately.

If it is impossible for Harry to reach any cell from which the trophy is visible, output -1.

Note: The line‐of‐sight in a given direction stops immediately when a wall is encountered. All intermediate cells between Harry and the trophy must be free (i.e. not walls) for the trophy to be visible.

inputFormat

The first line contains two integers n and m — the number of rows and columns of the maze.

The following n lines each contain a string of length m representing a row of the maze. The maze contains exactly one S (starting position) and exactly one T (trophy).

outputFormat

Output a single integer, the minimum time (in seconds) required for Harry to reach a cell from which the trophy is visible. If it is impossible, output -1.

sample

3 3
S..
.#.
..T

2