Treasure Collection on the Grid

Alice is navigating an n×m grid representing a city map. Each cell in the grid can contain one of the following characters:

• S: Starting position of Alice.
• T: A treasure that must be collected.
• .: An empty cell where Alice can walk.
• #: An obstacle that cannot be passed.

Alice can move in four directions: up, down, left, and right. The goal is to collect all treasures in minimum time. The time required is equal to the number of moves made. If it is impossible for Alice to collect all treasures, output -1.

The problem can be formulated as a traveling salesman problem (TSP) on the grid. Let \( d(u,v) \) be the minimum number of moves between two cells, computed via breadth-first search (BFS). You are required to compute the minimal total moves required to visit all treasure cells starting from the starting position:

[ \min_{\pi}; \left( d(S,\pi(1)) + \sum_{i=1}^{k-1} d(\pi(i), \pi(i+1)) \right) ]

where \(\pi\) is a permutation of all treasure positions.

inputFormat

The input is read from stdin and is structured as follows:

1. The first line contains two integers n and m, representing the number of rows and columns of the grid respectively.
2. Each of the next n lines contains a string of length m depicting a row of the grid.

outputFormat

Output a single integer representing the minimum time required to collect all treasures. If it is impossible to collect every treasure, output -1. The result should be written to stdout.

## sample

5 5
S..#T
.#.T.
.#...
.....
..T..

12

</p>