AT_abc427_e [ABC427E] Wind Cleaning

$ H $ 行 $ W $ 列のグリッドがあります。このグリッドの上から $ i $ 行目、左から $ j $ 列目のマスを $ (i, j) $ と表記します。 高橋君はこのグリッドの $ 1 $ つのマスの上におり、グリッド上のいくつかのマスにはゴミが落ちています。 各マスの状態は $ H $ 個の長さ $ W $ の文字列 $ S_1, S_2, \ldots, S_H $ によって与えられ、 $ S_i $ の $ j $ 文字目を $ S_{i, j} $ として、以下のような状態を表します。 - $ S_{i, j} = $ `T` のときマス $ (i, j) $ は高橋君がいるマスである。 - $ S_{i, j} = $ `#` のときマス $ (i, j) $ はゴミが落ちているマスである。 - $ S_{i, j} = $ `.` のときマス $ (i, j) $ はゴミが落ちていない空きマスである。 また、高橋君がいるマスにはゴミは落ちていません。 高橋君は、以下の操作を繰り返し行うことができます。 - 上下左右のいずれかの方向を $ 1 $ つ選び、すべてのゴミを同時にその方向へ $ 1 $ マス移動させる。ただし、ゴミがグリッドの外に出た場合にはゴミは消滅し、高橋君のいるマスにゴミが移動した場合は高橋君は汚れる。 高橋君が汚れることなくすべてのゴミを消滅させることができるか判定し、できる場合は操作を行う回数の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_H $

高橋君が汚れることなくすべてのゴミを消滅させることができる場合、操作を行う回数として考えられる最小値を出力せよ。そうでないとき、`-1` と出力せよ。

### Sample Explanation 1 高橋君は以下のように操作を行うことで $ 3 $ 回の操作ですべてのゴミを消滅させることができます。 - 上を選ぶ。この操作後、ゴミはマス $ (1, 1) $ とマス $ (2, 4) $ にある。 - 右を選ぶ。この操作後、ゴミはマス $ (1, 2) $ にある。 - 上を選ぶ。この操作後、すべてのゴミは消滅している。 ### Constraints - $ 2 \leq H, W \leq 12 $ - $ S_i $ は長さ $ W $ の `T`, `#`, `.` からなる文字列 - $ S_{i, j} = $ `T` なる $ (i, j) $ がちょうど $ 1 $ つ存在する - $ S_{i, j} = $ `#` なる $ (i, j) $ が $ 1 $ つ以上存在する