问题描述

有一个以 $H$ 行 $W$ 列的二维网格表示的城镇。
字符 $a_{i,j}$ 描述了从上方第 $i$ 行、从左边第 $j$ 列的方块。这里，$a_{i,j}$ 是以下之一：S, G, ., #, a, ..., 和 z。
# 表示无法进入的方块，a 到 z 表示带有传送门的方块。

高桥最初位于表示为 S 的方块上。每秒钟，他可以进行以下移动之一：

• 转移到当前位置水平或垂直相邻的非 # 方块。
• 选择与当前位置相同字符的方块，并传送到该方块。当他在一个表示为 a 到 z 的方块上时，只能使用此移动方式。

找出从表示为 S 的方块到表示为 G 的方块所需的最短时间。
如果无法到达目的地，则打印 -1。

约束条件

• $1 \le H, W \le 2000$
• $a_{i,j}$ 是 S, G, ., #, 或小写英文字母。
• 只有一个方块表示为 S，一个方块表示为 G。

输入

输入以以下格式从标准输入给出：

$H$ $W$

$a_{1,1}\dots a_{1,W}$

$\vdots$

$a_{H,1}\dots a_{H,W}$

输出

打印从表示为 S 的方块到表示为 G 的方块所需的最短时间。
如果无法从初始位置到达目的地，则打印 -1。

示例输入 1

2 5
S.b.b
a.a.G

示例输出 1

4

记 $(i, j)$ 为从上方第 $i$ 行、从左边第 $j$ 列的方块。
最初，高桥位于 $(1, 1)$。从 $(1, 1)$ 在四秒内到达 $(2, 5)$ 的一种方法是：

• 从 $(1, 1)$ 转移到 $(2, 1)$；
• 从 $(2, 1)$ 传送到 $(2, 3)$，它也是一个 a 方块；
• 从 $(2, 3)$ 转移到 $(2, 4)$；
• 从 $(2, 4)$ 转移到 $(2, 5)$。

示例输入 2

11 11
S##...#c...
...#d.#.#..
..........#
.#....#...#
#.....bc...
#.##......#
.......c..#
..#........
a..........
d..#...a...
.#........G

示例输出 2

14

示例输入 3

11 11
.#.#.e#a...
.b..##..#..
#....#.#..#
.#dd..#..#.
....#...#e.
c#.#a....#.
.....#..#.e
.#....#b.#.
.#...#..#..
......#c#G.
#..S...#...

示例输出 3

-1