题目描述

有一个矩形形状的池塘。池塘被划分为一个 $H$ 行 $W$ 列的方格网格。我们用 $(i, j)$ 表示从上到下第 $i$ 行、从左到右第 $j$ 列的方格。

池塘中一些方格上漂浮着莲叶。在其中一个叶子上，标记为 $S$，有一只青蛙试图跳到另一个叶子 $T$ 上。方格 $(i, j)$ 的状态用字符 $a_{ij}$ 表示，如下所示：

• .：没有叶子的方格。
• o：水面上带有叶子的方格。
• S：带有叶子 $S$ 的方格。
• T：带有叶子 $T$ 的方格。

青蛙将重复执行以下动作以到达叶子 $T$：「跳到与青蛙当前所在叶子在同一行或同一列的叶子上」。

Snuke 正试图除了 $S$ 和 $T$ 之外移除一些叶子，使得青蛙无法到达叶子 $T$。判断是否可以实现这个目标。如果可以实现，找到必须移除的最小叶子数。

约束条件

• $2 ≤ H, W ≤ 100$
• $a_{ij}$ 为 ., o, S 或 T。
• $a_{ij}$ 中恰好有一个 S。
• $a_{ij}$ 中恰好有一个 T。

输入

输入以以下格式从标准输入中给出：

$H$ $W$ $a_{11}$ $...$ $a_{1W}$ $:$ $a_{H1}$ $...$ $a_{HW}$

输出

如果可以实现目标，请打印必须移除的最小叶子数。否则，打印 -1。

示例输入1

3 3
S.o
.o.
o.T

示例输出1

2

移除右上角和左下角的叶子。

示例输入2

3 4
S...
.oo.
...T

示例输出2

0

示例输入3

4 3
.S.
.o.
.o.
.T.

示例输出3

-1

示例输入4

10 10
.o...o..o.
....o.....
....oo.oo.
..oooo..o.
....oo....
..o..o....
o..o....So
o....T....
....o.....
........oo

示例输出4

5