AT_abc436_d [ABC436D] Teleport Maze

$ H $ 行 $ W $ 列のマス目からなる迷路があります。 上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,j) $ と表記します。 マス $ (i,j) $ がどのようなマスであるかは文字 $ S_{i,j} $ として与えられ、各文字の意味は以下の通りです。 - `.` : 空きマス - `#` : 障害物マス - 英小文字（`a` - `z`）: ワープマス 迷路内では、以下の二種類の行動を好きな順序で何回でも行うことができます。 - 歩行：現在いるマスから上下左右の四方向のいずれかに $ 1 $ マス分進んだマスへ移動する。ただし、障害物マスへ移動することや、マス目の外に移動することはできない。 - ワープ：ワープマスにいるとき、そのワープマスと同じ文字が書かれたワープマスのうちいずれか好きなマスへと移動する。 マス $ (1,1) $ からマス $ (H,W) $ へ移動することが可能かどうか判定し、可能ならばそれに必要な最小の合計行動回数を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ S_{1,1}S_{1,2}\dots S_{1,W} $ $ \vdots $ $ S_{H,1}S_{H,2}\dots S_{H,W} $

マス $ (1,1) $ からマス $ (H,W) $ へ移動することが可能ならばそれに必要な最小の合計行動回数を、不可能ならば `-1` を出力せよ。

### Sample Explanation 1 以下のように行動することで、マス $ (1,1) $ からマス $ (3,4) $ へ移動することができます。 1. マス $ (1,1) $ からマス $ (1,2) $ へ歩行によって移動する。 2. マス $ (1,2) $ からマス $ (1,3) $ へ歩行によって移動する。 3. マス $ (1,3) $ からマス $ (3,2) $ へワープによって移動する。 4. マス $ (3,2) $ からマス $ (3,1) $ へ歩行によって移動する。 5. マス $ (3,1) $ からマス $ (3,4) $ へワープによって移動する。 このときの合計行動回数は $ 5 $ 回であり、これが最小です。 ### Sample Explanation 2 マス $ (1,1) $ からマス $ (3,4) $ へ移動することは不可能です。 ### Constraints - $ 1\leq H,W \leq 1000 $ - $ H\times W \geq 2 $ - $ H,W $ は整数 - $ S_{i,j} $ は `.`, `#`, または英小文字のいずれか - $ S_{1,1}\neq $ `#` - $ S_{H,W}\neq $ `#`