問題文

縦 H マス、横 W マスのグリッド状の迷路があり、上から i 行目・左から j 列目のマスを (i,j) とします。マス (i,j) は S_{i,j} = # のとき壁で、S_{i,j} = . のとき壁ではありません。

あなたは上下左右に隣接する壁でないマスへの移動を繰り返してマス (r_s,c_s) からマス (r_t,c_t) に移動したいです。ただし、移動する方向が変わる回数が多いと脳が疲れてしまうため好ましくありません。また、迷路の外へ出るような移動は許されません。

移動する方向が変わる回数の最小値を求めてください。

制約

• 2 \leq H,W \leq 1000
• 1 \leq r_s,r_t \leq H
• 1 \leq c_s,c_t \leq W
• (r_s,c_s) \ne (r_t,c_t)
• H,W,r_s,c_s,r_t,c_t は整数
• S_{i,j} は # または .
• S_{r_s,c_s},S_{r_t,c_t} は .
• マス (r_s,c_s) からマス (r_t,c_t) への移動が可能

入力例 1

3 3
1 1
3 3
..#
#.#
#..

出力例 1

2

最短路に沿って進むと、マス (1,2) とマス (3,2) で移動の方向が変わります。

入力例 2

3 3
2 1
2 3
#.#
...
#.#

出力例 2

0

入力例 3

4 6
2 1
1 5
...#..
.#.##.
.#....
...##.

出力例 3

5