Island Hopping

Farmer John has taken the cows on an ocean vacation, and the cows are now residing on N islands on an R x C grid. Each cell in the grid is marked with one of three characters: X (land), S (shallow water), or . (deep water). An island is defined as a maximal group of connected X cells (two cells are connected if they share a side). Bessie may initially land on any island. She can move in the four cardinal directions (north, east, south, west) on islands and shallow water, but she cannot step into deep water.

Bessie wants to visit every island at least once. When she moves, she can go from an island to a shallow water cell and vice versa; however, each time she steps on a shallow water cell it counts as 1 unit of swimming effort. Moving on islands costs nothing. Your task is to determine the minimum total swimming cost (i.e. the number of shallow water cells she must traverse) required for Bessie to visit all islands. It is guaranteed that a valid path exists.

Formally, let the cost of stepping into a cell marked S be 1, and the cost for an island cell (X) be 0. Given that Bessie may choose any island to land on initially, compute the minimum total cost necessary to traverse all islands at least once. In mathematical terms, if we denote the cost along a path as \(\sum_{\text{step}} c(\text{cell})\) where \(c(\text{cell})=1\) if the cell is shallow water and 0 if it is land, find the minimum cost required over all possible routes that cover every island.

Note: Two X cells are considered part of the same island if they are adjacent by sides. Movements on the grid are only allowed in the four cardinal directions.

inputFormat

The first line contains two integers R and C (1 ≤ R, C ≤ 50), representing the number of rows and columns of the grid respectively. The following R lines each contain a string of C characters which are either X (land), S (shallow water), or . (deep water).

outputFormat

Output a single integer: the minimum number of shallow water (S) cells that Bessie must travel through in order to visit every island at least once.

sample

3 3
XSS
SSX
XSS

2