题目描述

有一个长方形的池塘。池塘被分割为高 $H$ 行、宽 $W$ 列的网格。从上往下第 $i$ 行，从左往右第 $j$ 列的格子可以表示为 $(i,\, j)$。

池塘中的某些格子上漂浮着莲叶。某只青蛙正站在编号为 $S$ 的叶子上，准备移动到另一个编号为 $T$ 的叶子。每个格子 $(i,\, j)$ 的信息由字符 $a_{ij}$ 表示：

• . ：该格子上没有莲叶。
• o ：该格子上有一片莲叶。
• S ：该格子上有编号为 $S$ 的莲叶。
• T ：该格子上有编号为 $T$ 的莲叶。

青蛙可以不断进行如下操作：“跳到当前所在叶子同一行或同一列上漂浮的另一个叶子上”。青蛙希望移动到叶 $T$。

すぬけ君的目标是，提前移除若干（可以为零）片叶子（不能移除 $S$ 和 $T$），使得青蛙无法从 $S$ 移动到 $T$。请判断能否实现该目标。如果可以，请输出最少需要移除的叶子数量。如果不能实现，请输出 $-1$。

输入格式

输入为如下格式，从标准输入读入。

$H$ $W$
$a_{11} a_{12} ... a_{1W}$
$\vdots$
$a_{H1} a_{H2} ... a_{HW}$

输出格式

如果目标可以实现，输出最少需要移除的叶子的数量。否则，请输出 $-1$。

样例 1

输入

3 3
S.o
.o.
o.T

输出

2

样例 2

输入

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

输出

0

样例 3

输入

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

输出

-1

样例 4

输入

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

输出

5

说明/提示

限制

• $2 \leq H, W \leq 100$
• $a_{ij}$ 只会是 ., o, S, T 之一。
• 所有 $a_{ij}$ 中恰好有一个 S。
• 所有 $a_{ij}$ 中恰好有一个 T。

样例解释 1

只需移除右上和左下的两片叶子即可。

由 ChatGPT 5 翻译