### 问题描述 小齐和她的牛牛们正在进行一场海岛度假。这片海域有 $N$（$1 \leq N \leq 15$）个岛屿，它们分布在一个 $R \times C$（$1 \leq R, C \leq 50$）的方格网格上。每个岛屿都是由标记为 $X$ 的相邻方格组成的最大连通区域构成，其中两个 $X$ 方格如果共享一条边则被视为相邻（因此，共享角点的两个 $X$ 不一定相邻）。 由于小齐迟到了，所以她和农夫约翰一同乘坐直升机抵达。她可以选择首先降落在任何一个岛上。小齐希望至少访问每个岛一次，因此她将在岛屿之间穿越，直到她至少访问过所有 $N$ 个岛。 约翰的直升机剩余燃料不多，所以他不希望在牛牛们决定回家之前就用光燃料。幸运的是，方格网格中的一些方格是浅水，用 $S$ 表示。小齐可以沿着这些方格在四个基本方向（北、东、南、西）上下游泳，以在岛屿之间进行移动。她还可以在岛屿和浅水之间自由移动，反之亦然。 找出小齐为了访问所有岛屿而必须游泳的最短距离（小齐游泳的距离是她站在标记为 $S$ 的方格上的次数）。在查看了该地区的地图后，小齐知道这是可能的。 ### 输入格式 第 $1$ 行：两个用空格分隔的整数 $R$ 和 $C$。 第 $2$ 行到第 $R+1$ 行：每行包含 $C$ 个字符，表示网格的每一行。深水方格用 $.$ 表示，岛屿方格用 $X$ 表示，浅水方格用 $S$ 表示。 ### 输出格式 一个整数，表示小齐为了访问所有岛屿而必须游泳的最短距离。 ### 样例输入 ``` 5 4 XX.S .S.. SXSS S.SX ..SX ``` ### 样例输出 ``` 3 ``` ### 评测数据规模 $1 \leq R, C \leq 50$，$1 \leq N \leq 15$。