크기가 \(h \times w\)인 미로가 있다. 이 미로는 길과 벽으로 구성되어 있으며, 길은 ".", 벽은 "#"으로 구성되어 있으며, 시작위치 "S"와 도착위치 "G"가 존재한다.

위에서 제시한 각 정보가 주어질 때, S위치로부터 G위치까지의 최단 거리를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 \(h\)와 \(w\)가 공백으로 구분되어 입력된다.

두 번째 줄부터 \(h\)줄에 걸쳐서 \(w\)개로 이루어진 문자열이 입력된다.

문자열은 길은 ".", 벽은 "#", 출발점은 "S", 도착점은 "G"로 표시된다.

출력

출발지로부터 도착지까지의 최단거리를 출력한다. 단, 도달할 수 없는 미로일 경우에는 -1을 출력한다.

제한사항

• \(5 \le h, w \le 100\) (\(h, w\)는 자연수)
• 출발점 "S"와 도착점 "G"의 위치는 서로 다르며, 미로 전체에서 각각 정확히 1개씩만 존재한다.

예제 입력 1

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

예제 출력 1

6

예제 입력 2

5 5
S####
#####
#####
#####
####G

예제 출력 2

-1