Minimum Seconds to Reach Destination

You are given a grid city map where each cell is either an open road ., an obstacle #, a starting point S, or a destination E. The goal is to determine the minimum number of seconds needed for a car to move from the start to the destination. In one second, the car can move one cell up, down, left, or right.

If there is no valid path from S to E (i.e. the destination cannot be reached), output -1.

The movement obeys the following rule:

• Only adjacent cells (up, down, left, or right) that are not blocked by obstacles (i.e. cells that are not #) can be visited.

The computation is essentially a breadth-first search (BFS) on the grid. The distance between two adjacent cells is 1 second, so if the coordinates of the start and destination are \( (x_s, y_s) \) and \( (x_e, y_e) \), respectively, a valid path with total distance \( d \) seconds will be computed. The answer is \( d \) if a valid path exists, or \( -1 \) if the destination cannot be reached.

inputFormat

The input is read from stdin and formatted as follows:

T
N1 M1
row1
row2
... (N1 rows)
N2 M2
row1
row2
... (N2 rows)
...

Here, T is the number of test cases. For each test case, N and M represent the number of rows and columns, respectively, followed by N lines each containing a string of length M that represents one row of the city map.

outputFormat

For each test case, print a single integer in a new line to stdout that represents the minimum time (in seconds) required for the car to reach the destination. If the destination is unreachable, print -1.

## sample

4
3 3
S..
.#.
..E
3 3
S#.
###
.#E
1 3
SE.
9 9
S........
.........
.........
.........
.........
.........
.........
.........
........E

4
-1
1
16

</p>