题目描述

农夫约翰带着奶牛去海边度假！奶牛生活在 $\red{N (1 <= N <= 15) }$个岛屿上，这些岛屿位于 $\red{R x C }$网格 $\red{(1 <= R, C <= 50) }$上。岛是网格上标记为"$\red{X}$"的最大连通方组，其中如果两个"$\red{X}$"共享一条边，则它们是连接的。（因此，共享一个角的两个"$\red{X}$"不一定是相连的。）

然而，$\red{Bessie }$来晚了，所以她和 $\red{FJ }$坐直升机进来。因此，她可以首先登陆她选择的任何岛屿。她想至少访问所有的奶牛一次，因此她将在岛屿之间旅行，直到她至少访问了所有 $\red{N }$个岛 屿一次。

$\red{FJ }$的直升机没有多少燃料了，所以在奶牛决定回家之前他不想使用它。幸运的是，网格中的一些方格是浅水区，用"$\red{S}$"表示。贝西可以在四个主要方向（北、东、南、西）游过这些广场，以便在岛 屿之间旅行。她还可以（在四个主要方向）在岛屿和浅水之间旅行，反之亦然。

找出贝西必须游泳的最短距离才能访问所有岛屿。（$\red{Bessie }$必须游泳的距离是她在标有"$\red{S}$"的正方形上的不同次数。）查看该区域的地图后，$\red{Bessie }$知道这是可能的。

给你一张$\red{r \times c}$的地图，有’$\red{S}$’,’$\red{X}$’,’.’三种地形，所有判定相邻与行走都是四连通的。我们设’$\red{X}$’为陆地，一个’$\red{X}$’连通块为一个岛屿，’$\red{S}$’为浅水，’.’为深水。刚开始你可以降落在任一一块陆地上，在陆地上可以行走，在浅水里可以游泳。并且陆地和浅水之间可以相互通行。但无论如何都不能走到深水。你现在要求通过行走和游泳使得你把所有的岛屿都经过一边。$\red{Q：}$你最少要经过几个浅水区？保证有解。

输入格式

第 $\red{1 }$行：两个空格分隔的整数：$\red{R }$和 $\red{C}$。

第 $\red{2..R+1 }$行：第 $\red{i+1 }$行包含 $\red{C }$个字符，给出网格的第 $\red{i }$行。深水方块标记为"."，岛屿方块标记为"$\red{X}$"，浅水方块标记为"$\red{S}$"。

输出格式

第 $\red{1 }$行：一个整数，表示 $\red{Bessie }$必须游到所有岛屿的最短距离。

样例

输入样例

5 4 
XX.S
..
SXSS
S.SX 
..SX

输出样例

3

提示

有三个岛屿，其中一些岛屿有浅水路径连接。

$\red{Bessie }$可以从左上的小岛游到中间的小岛，游泳 $\red{1 }$个单位，然后从中间的小岛游到右下的小岛，游泳 $\red{2 }$个单位，总共 $\red{3 }$个单位。