题目描述

给定一个 $n$ 行 $m$ 列的迷宫。字符“#”表示墙壁，字符“.”表示可以行走的格子，字符“S”表示起点。

你每次可以从当前格子移动到上下左右相邻的一个非墙壁格子。现在需要从起点“S”出发，沿着一条环路最终回到“S”。除了起点作为首尾位置外，同一个格子不能在环路中重复出现。

请计算经过边数最少的环路长度。如果不存在这样的环路，输出 $-1$。

输入格式

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

接下来 $n$ 行，每行包含 $m$ 个字符，描述迷宫。地图中恰好有一个字符“S”。

输出格式

输出经过起点的最短环路长度。如果不存在环路，输出 $-1$。

样例

输入

4 4
....
#.#.
.S..
.##.

输出

8

4 4
....
#.#.
.S..
.##.

8

8 5
....#
....#
.....
.....
.....
.##..
..S.#
.....

4

11 4
.#..
..S.
....
#...
....
.#..
...#
#...
..#.
##..
....

4