配点 : $800$ 点

問題文

長方形の池があります。 池は縦 $H$ 行、横 $W$ 列のマス目状に分割されています。 上から $i$ 行目、左から $j$ 列目のマスを $(i,\ j)$ と表します。

池のいくつかのマスには蓮 (はす) の葉が浮かんでいます。 ある葉 $S$ にはカエルが乗っており、別の葉 $T$ まで移動しようとしています。 マス $(i,\ j)$ の情報は、文字 $a_{ij}$ によって次のように表されます。

• . : 葉が浮かんでいないマスである。
• o : 葉が浮かんでいるマスである。
• S : 葉 $S$ が浮かんでいるマスである。
• T : 葉 $T$ が浮かんでいるマスである。

カエルは「今乗っている葉と同じ行または同じ列に浮かんでいる葉へジャンプする」ことを繰り返し行い、葉 $T$ まで移動しようとしています。

すぬけ君の目標は、あらかじめ葉 $S$, $T$ 以外の葉を何枚か取り除いておくことで、カエルが葉 $T$ まで移動できないようにすることです。 この目標が達成可能か判定し、可能ならば取り除く葉の枚数の最小値を求めてください。

制約

• $2 \leq H, W \leq 100$
• $a_{ij}$ は ., o, S, T のどれかである。
• $a_{ij}$ のうち S はちょうど $1$ 個存在する。
• $a_{ij}$ のうち T はちょうど $1$ 個存在する。

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$

$a_{11}$ $...$ $a_{1W}$

$:$

$a_{H1}$ $...$ $a_{HW}$

出力

目標が達成可能ならば、取り除く葉の枚数の最小値を出力せよ。 そうでなければ、代わりに -1 を出力せよ。

3 3
S.o
.o.
o.T

2

右上と左下の葉を取り除けばよいです。

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

0

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

-1

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

5