Problem F
Hurricane Maple Syrup

Image created using ChatGPT

This year a harsh Atlantic hurricane season is predicted. You are a maple syrup producer who owns a number of maple tree stands all within a particular geographic region, and so the harsh hurricane prediction is troubling for you. You know that a hurricane has the potential to blow down a tree stand, but you also know that if a tree stand is shielded from the wind then it can survive a hurricane without issue.

A map of the geographic region is presented as a grid of letters in which your maple tree stands are denoted with the letter M, other tree stands are denoted with T, low areas like lakes, bogs, or fields are denoted with L, and solid structures like barns are denoted with S. Any tree stand (M or T) that is adjacent to other tree stands or solid structures (M, T, or S) on all four sides (north, south, east, and west) will survive a hurricane. But any tree stand that is on a boundary square, or is adjacent to a low area or a tree stand that was already destroyed, will be destroyed by a hurricane.

In a harsh hurricane season, many hurricanes could hit your region. Your task is to determine the minimum number of hurricanes it would take to destroy all of your maple stands, or if at least one of your maple stands can survive any number of hurricanes.

For example, suppose your region is given by:

      LML
      LML
      SMT
      LML

After one hurricane hits your region, it would look like this (where X denotes a destroyed tree stand):

      LXL      
      LXL      
      SMX      
      LXL      

If a second hurricane hits your region, it would then look like this:

      LXL      
      LXL      
      SXX      
      LXL      

Thus in the above example it would take $2$ hurricanes to destroy all of your maple stands.

Input

The first line of input contains two space-separated integers, $R$ $(1 \leq R \leq 1000)$ and $C$ $(1 \leq C \leq 1000),$ the number of rows and columns in the map, respectively. This is followed by the map, given as $R$ lines containing $C$ characters each, with all characters from the set $\{ \texttt{M}, \texttt{T}, \texttt{L}, \texttt{S} \} .$ It is guaranteed that the map will contain at least one M.

Output

Output a single integer: the minimum number of hurricanes it would take to destroy all of your maple stands, or $-1$ if at least one maple stand would survive any number of hurricanes.

4 3
LML
LML
SMT
LML

2

4 3
LML
LLL
SMT
LLL

1

3 4
SSSM
SMSL
SSSL

-1

5 5
MMMMM
MMMMM
MMMMM
MMMMM
MMMMM

3