题目描述

一座城市由 $H$ 行 $W$ 列网格表示。每格为以下字符之一：S、G、.、# 或小写英文字母。 S 是起点，G 是终点，. 是普通格，# 是不能进入的障碍，小写字母表示传送格。

你从 S 出发，每秒可以选择以下一种移动：

• 走到上下左右相邻的一个非障碍格。
• 若当前格是小写字母，可以传送到任意一个具有相同字母的格子。

传送是可选操作，且本身也消耗一秒。求到达 G 的最短时间；无法到达时输出 -1。

输入格式

第一行两个整数 $H,W$。接下来 $H$ 行，每行长度为 $W$ 的字符串，描述网格。

输出格式

输出最短时间；无法到达时输出 -1。

数据范围

$1\le H,W\le2000$。网格仅包含 S、G、.、# 或小写英文字母。恰好有一个 S 和一个 G。

样例 1

2 5

S.b.b

a.a.G

4

四秒路线：(1,1)→(2,1)，传送到同为 a 的 (2,3)，再走到 (2,4)、(2,5)。

样例 2

11 11

S##...#c...

...#d.#.#..

..........#

.#....#...#

#.....bc...

#.##......#

.......c..#

..#........

a..........

d..#...a...

.#........G

14

样例 3

11 11

.#.#.e#a...

.b..##..#..

#....#.#..#

.#dd..#..#.

....#...#e.

c#.#a....#.

.....#..#.e

.#....#b.#.

.#...#..#..

......#c#G.

#..S...#...

-1