Shortest Path in a Maze

In this problem, you are given a maze represented by a grid with n rows and m columns. Each cell of the maze is represented by one of the following characters:

• S: the start cell
• G: the goal cell
• .: an open cell that you can traverse
• #: a wall that you cannot pass

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

The distance is measured in the number of steps taken. Mathematically, if you denote a move by a step of 1 in one of the four directions, then the problem is to find the minimum number of steps such that:

\( \min \{ d \mid S \rightarrow G \} \)

where d is the number of moves, and if no such sequence exists, print -1.

inputFormat

The input is given via standard input (stdin) and has the following format:

n m
row1
row2
... 
rown

Here:

• n and m are positive integers representing the number of rows and columns respectively.
• Each of the next n lines contains a string of length m that represents a row of the maze.

outputFormat

Output the length of the shortest path from S to G via standard output (stdout). If such a path does not exist, print -1.

## sample

4 5
S.###
...#G
##...
####.

7