NJU杰哥

Description

为了更加快乐的PA,NJU的杰哥决定练习一下vim的一些常用按键.在小明的推荐下,杰哥接触了一款练习方向键的迷宫游戏.游戏中给出了一个\(N\times M\)的迷宫,迷宫由通道和墙壁组成.规则是从迷宫的起点出发走到迷宫的终点(只有上下左右四种方向).杰哥希望知道每一关需要走的最少步数以确定自己是否有可能在规定时间内通过此关.杰哥听说你刚自学了基本的图算法,于是请你写一个程序帮他确定从迷宫起点到达终点需要的最少步数.

Input

每组测试包含一个测试样例.

第一行为两个整数\(N,M\)(\(1\leq N,M\leq 100\),且N,M不同时为1)表示了迷宫的大小.接下来的\(N\)行给出了迷宫的形状.'#','.','S','G'分别表示墙壁,通道,起点和终点.

Output

输出从起点走到终点需要的最少步数.(本题假设从起点一定能走到终点)

Sample Input

10 10
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#

---

2 1
SG

Sample Output

22

---

1