Shortest Path in Labyrinth

You are given a rectangular labyrinth represented by a grid with R rows and C columns. Each cell in the labyrinth is either:

• a free cell ('.')
• an obstacle ('#')
• the entrance ('E')
• the treasure ('T')

Your task is to determine the length of the shortest path from the entrance to the treasure, moving only in the four cardinal directions (up, down, left, right), and you cannot traverse obstacles.

If there is no valid path, output -1.

The problem can be modeled using a Breadth-First Search (BFS) algorithm. In mathematical terms, if we denote the Manhattan distance between two adjacent cells as \(1\), then the length of a path is the sum of the distances between consecutive cells. That is, if a path consists of cells \(c_1, c_2, \dots, c_k\), its length is

\[ \sum_{i=1}^{k-1} 1 = k-1. \]

inputFormat

The input consists of multiple test cases. Each test case starts with a line containing two integers R and C (\(1 \le R, C \le 1000\)). The next R lines each contain a string of length C representing a row of the labyrinth.

The input is terminated by a line with "0 0", which should not be processed.

outputFormat

For each test case, output a single integer on a separate line representing the length of the shortest path from the entrance ('E') to the treasure ('T'). If no such path exists, output -1.

## sample

6 7
E......
.###...
.#.....
.#.###.
....#T.
.......
0 0

11