Shortest Path in a Grid

You are given an n x m grid that represents a terrain. Each cell in the grid can be:

• S: the starting point
• E: the destination point
• #: an obstacle (cannot be traversed)
• .: an open space

Your task is to find the length of the shortest path from S to E, moving only in the four cardinal directions (up, down, left, right). If there is no valid path, output -1.

The shortest path length d is defined as the minimum number of moves required to reach E from S:

\( d = min_{\text{valid path}} (\text{number of moves}) \)

Read the input from standard input and output the result to standard output.

inputFormat

The input is read from standard input and has the following format:

 n m
 row1
 row2
 ...
 row_n

Where:

• n and m are integers representing the number of rows and columns respectively.
• Each of the next n lines contains a string of length m representing a row in the grid.

outputFormat

Output a single integer to standard output. This integer is the length of the shortest path from S to E. If no such path exists, output -1.

## sample

5 5
S...#
..#.#
#.##.
..#.E
.....#

9