Geunsoo's Maze Game

Geunsoo and Seunghyeong want to play Geunsoo's maze game. The maze is a grid of $N \times M$ cells made of empty cells, obstacles, one start cell, and goal cells. The maze has exactly one start cell. It may have one or more goal cells, or none at all.

Geunsoo starts at the start cell. Every goal cell holds a Dokma Umaru doll that Geunsoo likes, so Geunsoo wants to move to one of the goal cells. Seunghyeong wants to block Geunsoo as much as possible. Each turn, the two repeat the following until the game ends.

1. If the current position is a goal, Geunsoo wins.
2. If the current position is not a goal, Seunghyeong picks one of four directions (up, down, left, or right).
3. Geunsoo picks one of the three directions other than the one Seunghyeong picked and moves one cell in that direction. If the target cell is an obstacle, Seunghyeong wins immediately. If the target cell was already visited or is outside the grid, Seunghyeong wins immediately.

Geunsoo wants to win, and if he wins, he wants to reach a goal in as few turns as possible. Seunghyeong wants to win, and if he cannot win, he wants Geunsoo to take as many turns as possible to reach a goal. Assuming both play optimally, find whether Geunsoo can win, and if so, how many turns it takes to reach a goal.

The first line contains $N$ and $M$ ($1 \leq N, M \leq 500$), the size of the maze.

The next $N$ lines describe the maze. . is an empty cell, # is an obstacle, S is the start cell, and G is a goal cell. There is exactly one S. There may be one or more G cells, or none.

Print the number of turns it takes Geunsoo to reach a goal, assuming both play optimally. If Geunsoo cannot win, print -1.