Problem Description

You found a suspicious maze generator on the street. When activated, it automatically generates a maze of height $ H $ and width $ W $. However, it has a flaw and generates mazes that cannot reach the goal. Therefore, you decided to fix the maze so that it becomes possible to reach the goal.

The maze contains walls # and paths ., with one start cell S and one goal cell G. The player starts from the start cell and moves to adjacent cells (up, down, left, right) that are not walls, aiming for the goal cell. You decided to change exactly one wall cell to a path cell to make the maze solvable.

However, you thought it would be boring to just change any wall to a path. Instead, you decided to change a wall to a path in such a way that the shortest path length from the start to the goal is maximized.

Answer the shortest path length from the start to the goal after performing the above operation.

Input Format

$ H $ $ W $ $ line_1 $ $ line_2 $ ... $ line_H $

• The first line contains the height $ H $ and width $ W $ of the maze $(2 \leq H, W \leq 298)$.
• The next $ H $ lines contain a string $ line_i $ of $ W $ characters each. Each $ line_i $ (1 \leq i \leq H) consists of #, ., S, G, where # represents a wall, . represents a path, S represents the start point, and G represents the goal point.

Note that there is always exactly one S and one G in the maze.

The given maze is guaranteed to be unsolvable from S to G, but changing exactly one wall to a path will make it solvable.

Output Format

Output the shortest path length to the goal in the fixed maze in one line. End the output with a newline.

Sample Input and Output

Sample Input #1

6 8
S..#...#
##...#..
..###.##
........
.#######
.......G

Sample Output #1

28

Sample Input #2

5 6
#.S.#.
###...
...###
.#.#.G
.....#

Sample Output #2

10

Sample Input #3

4 6
S.....
###.##
######
.....G

Sample Output #3

8

Sample Input #4

6 8
S.......
########
...#....
.##..##.
...#.#..
.#.G#..#

Sample Output #4

12

Sample Input #5

7 8
.#......
S#.#.###
...#.#.#
###.#.G.
.....#..
..##.#.#
........

Sample Output #5

14

Notes/Hints

Sample Explanation 2

There can be loops in the path.

Sample Explanation 3

There can be thick walls.

Sample Explanation 4

There can be paths that are not connected to either S or G initially.

见题面 Input 部分

见题面 Output 部分