근수의 미로게임

근수와 승형이는 근수의 미로게임을 즐기려고 한다. 미로는 $N \times M$ 크기의 격자판이며, 빈 칸, 장애물, 시작점, 도착점으로 이루어져 있다. 시작점은 단 한 개이고, 도착점은 한 개 이상일 수도 있고 없을 수도 있다.

근수는 시작점에서 출발한다. 모든 도착점에는 근수가 좋아하는 도마 우마루 인형이 놓여 있어서, 근수는 도착점 중 한 곳으로 이동하려고 한다. 승형이는 근수를 최대한 방해하려고 한다. 근수와 승형이는 게임이 끝날 때까지 다음 턴을 반복한다.

1. 현재 위치가 도착점이라면 근수가 승리한다.
2. 현재 위치가 도착점이 아니라면 승형이가 위, 아래, 왼쪽, 오른쪽 중 한 방향을 고른다.
3. 근수는 승형이가 고른 방향을 제외한 세 방향 중 한 방향을 골라 한 칸 이동한다. 이동할 칸에 장애물이 있으면 승형이가 즉시 승리한다. 이동할 칸이 이미 방문한 칸이거나 격자판 밖이면 승형이가 즉시 승리한다.

근수는 이기고 싶어 하며, 이길 수 있다면 도착점에 도달하는 턴 수를 최대한 줄이고 싶어 한다. 승형이는 이기고 싶어 하며, 이기지 못한다면 근수가 도착점에 도달하는 턴 수를 최대한 늘리고 싶어 한다. 두 사람이 항상 최선의 전략으로 게임한다고 가정할 때, 근수가 이길 수 있는지, 이긴다면 도착점에 도달할 때까지 몇 턴이 걸리는지 구해보자.

첫 번째 줄에 미로의 크기인 $N$, $M$이 주어진다 $(1 \leq N, M \leq 500)$.

두 번째 줄부터 $N+1$번째 줄까지 미로에 대한 정보가 주어진다. .은 빈 칸, #은 장애물, S는 시작점, G는 도착점을 뜻한다. 시작점은 반드시 한 개 있으며, 도착점은 한 개 이상일 수도 있고 없을 수도 있다.

근수와 승형이가 항상 최선의 전략으로 게임한다고 가정할 때 근수가 도착점에 도달하는 턴 수를 출력한다. 근수가 게임에서 이길 수 없다면 -1을 출력한다.