Minimum Number of Animals

You are given an H×W grid initially filled with a dot ('.'). Two types of animals – fox and rabbit – may have walked on this grid. When an animal traverses a cell, it leaves its mark: a fox leaves an 'F' and a rabbit leaves an 'R'. The animals start at the top‐left cell and finish at the bottom‐right cell. They can move freely up, down, left, or right (no diagonal moves or jumping cells are allowed) and they may even retrace their steps. Also, no two animals are on the grid at the same time. Importantly, if a cell is visited more than once, the mark left by the later animal overwrites what was there before.

Your task is: given the final grid configuration, determine the minimum number of animals that must have walked on the grid to produce that configuration.

Observations:

• Every animal’s path is from the top‐left cell to the bottom‐right cell.
• Because each animal marks every cell it visits with its own letter, a single animal’s path (if not overwritten later) will have only one type of mark.
• Since the last animal to traverse the grid will visit both the top‐left and bottom‐right corners, these two cells in the final configuration must contain the same letter. Let this letter be X.
• Any cell in the grid that is not a dot and does not contain X must have been visited by an earlier animal – meaning that one animal (with mark X) could have avoided covering those cells. Since the animals may take arbitrarily winding paths (backtracking is allowed), a single animal’s path can visit any set of cells if required.

Thus, if every visited cell (i.e. every character different from '.') in the final grid is X, it is possible that only one animal walked on the grid. Otherwise, at least two animals are needed. It turns out that two animals are always enough when the grid is otherwise valid.

inputFormat

The first line contains two integers H and W (the number of rows and columns). Each of the following H lines contains a string of length W consisting only of characters '.', 'F' and 'R'.

outputFormat

Output a single integer — the minimum number of animals that must have walked on the grid.

sample

3 3
FFF
FFF
FFF

1