AT_oidashi_a.不完全迷路

假如你在路旁捡到一个奇怪的迷宫生成器。 只要动一下它，就会自动生成很多纵长H，横长W的迷宫。 但是有时却会有缺陷，生成无法找到出口的迷宫。 所以，你需要修正这些迷宫，使它们能够找到出口。
对于迷宫，墙壁为#，路为...，起点为S，终点为G。玩家从起点开始移动，向相邻的长宽为4的非墙壁区域移动，到达终点。你需要从这里开始，将墙壁换成大小为1的道路，使其成为能够找到出口的迷宫。
但是，恰到好处的墙壁换成了路就没意思了。所以，你的修改必须使从起点到终点的最短路长变得最长。
请答出：经过了上述操作后，起点到终点的最短路长。

第一行，输入迷宫的纵长HHH，横长W(2≤H,W≤298)W(2 ≤ H, W ≤ 298)W(2≤H,W≤298)。
第二行及以下的H行，每行W个字符的语句lineiline_ilinei​，每个linei(1≤i≤H)line_i(1 ≤ i ≤ H)linei​(1≤i≤H)都由#，.，S，G构成，墙壁为#，路为.，起点为S，终点为G。而且，一个迷宫中S，G都有且仅有一个。
请保证：输入的迷宫，从S无法到达G，必须有一个墙壁被换成了路，迷宫才能找到出口。

输出修正后的迷宫起点到终点的最短路长。输出的末尾要换行。