Robot Path Planning

You are given a grid representing a map for a robot. The grid has N rows and M columns, where each cell is either free or blocked by an obstacle. The grid contains exactly one start cell marked with 'S' and one goal cell marked with 'G'. The robot can move one step at a time in the four cardinal directions (up, down, left, and right) and cannot pass through obstacles.

Your task is to determine the minimum number of steps required for the robot to move from the start to the goal. If there is no valid path, output -1.

The grid constraints are given by \( 1 \leq N, M \leq 1000 \). The input contains multiple datasets. Each dataset is formatted as follows:

• The first line contains two integers N and M separated by a space.
• The following N lines each contain a string of M characters representing the grid. Each character is one of:
• . : free cell
• # : obstacle
• S : start position
• G : goal position
• The input terminates with a line containing "0 0".

For example:

3 4
S...
.#..
...G
0 0

In this case, the minimum number of steps required is 5.

inputFormat

The input is given via stdin and consists of multiple datasets.

Each dataset is organized as follows:

• The first line contains two integers N and M (number of rows and columns).
• The next N lines each contain a string of exactly M characters where each character is either ., #, S, or G.
• A line with "0 0" indicates the end of the input.

outputFormat

For each dataset, output a single integer on a new line to stdout representing the minimum steps required to reach the goal from the start. If no valid path exists, output -1.

## sample

3 4
S...
.#..
...G
0 0

5