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，必须有一个墙壁被换成了路，迷宫才能找到出口。

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

### Sample Explanation 2 ループするような道もありえます ### Sample Explanation 3 厚い壁もありえます ### Sample Explanation 4 最初から`S`、`G`どちらとも繋がっていない道もありえます