珅泽教育的刘老师正在准备一项寻路实践，他请小珅完成下面的任务。

一张 $H$ 行 $W$ 列地图中，字符 S 是起点，G 是终点，# 是墙，. 是道路，小写字母 a 到 z 表示传送门。每一步可以走到上下左右相邻的非墙格；站在字母格时，还可以用一步传送到地图中任意另一个相同字母格。

请输出从 S 到 G 的最少步数；若无法到达，输出 $-1$。

输入格式

第一行输入 $H,W$。

接下来 $H$ 行输入地图。

输出格式

输出最少步数，无法到达输出 -1。

4 5
Saa..
.....
.....
..aaG

3

5 6
Saaa..
......
......
......
..aaaG

3

6 7
Saaaa..
.......
.......
.......
.......
..aaaaG

3

数据范围与约定

• $1 \le H,W \le 2000$
• 恰有一个 S 和一个 G