A116898.小午历险记之沙漠信标

在一片被风沙覆盖的无人区中，有一张由方格组成的探测区域图。小午需要从起点 $S$ 出发，前往目标信标 $T$。

地图中每个字符的含义如下：

• .：普通沙地，可以通行；
• #：岩壁，无法通过；
• G：能量检查点；
• S：起点；
• T：终点。

小午每一步可以向上 / 下 / 左 / 右移动一格（不能走出地图范围）。在整个行进过程中，最多只能通过一次能量检查点：也就是说，路径上最多进入 $1$ 个 G 格子；进入该格子的那一步同样计入步数。

请计算从 S 到 T 的最少步数；如果无法到达，输出 -1。

第一行包含两个整数 $n, m$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，表示探测区域地图。

保证地图中恰好有一个 S 和一个 T。

输出一个整数，表示最少步数；若无法到达，则输出 -1。

样例解释

最短路径需要恰好经过一次能量检查点，在避开岩壁后成功抵达目标信标。

数据范围

对于 $100\%$ 的测试数据，满足：$1\le n,m$ , $n\cdot m\le 2\times 10^5$