Minimum Additional Fence for Sheep-Wolf Separation

Orez’s sheep‐wolf enclosure is represented by an $n \times m$ grid. The outer boundary of the grid is already fenced. Some cells contain a wolf (denoted by 'W'), some contain a sheep (denoted by 'S'), and the remaining cells are empty (denoted by '.'). Initially there are no internal fences, so all cells are connected. However, since wolves will always covet sheep, Orez wants to add extra fences along the entire boundaries between grid cells (the fence must be built completely along the edge of a cell, not partially) in order to separate the wolves and the sheep.

Moreover, an important observation is that each wolf (or sheep) has its own territory. This means that all cells originally containing the same animal (if adjacent by a common side) are considered a single territory. When adding the extra fence, you must not break the connectivity of cells that originally belong to the same animal. In other words, the additional fence must not change the initial territory assignment of any wolf or sheep. Note that empty cells can be assigned arbitrarily to either territory.

Formally, you are given the grid. You must assign a binary label to every cell: label 0 for wolf territory and label 1 for sheep territory. For each adjacent pair of cells (sharing a side), if the labels differ, you incur a cost of 1 (this represents a fence segment). Cells that originally contain a wolf must be assigned label 0 and cells with a sheep must be assigned label 1. The goal is to choose an assignment for the empty cells ('.') so that the cost (the total length of additional fence) is minimized. However, if any two adjacent cells already contain different animals, then it is impossible to add fences without splitting an existing territory, and you should output -1.

Your task is to compute the minimum additional fence length needed. If it is impossible to separate the animals without breaking their original territories, output -1.

inputFormat

The first line contains two integers $n$ and $m$ --- the number of rows and columns.

Then follow $n$ lines, each containing a string of length $m$. Each character is one of W (wolf), S (sheep), or . (empty cell).

outputFormat

Output a single integer --- the minimum additional fence length required. If it is impossible to separate the wolves and sheep without breaking their original territories, output -1.

sample

3 3
...
.W.
..S

1