题目描述

$H$ 行 $W$ 列のグリッド型のスケート場があります。上から $i$ 行目、左から $j$ 行目のマスを $(i,j)$ で表します。

スケート場には $N$ 個の障害物があり、$i$ 個目の障害物は $(X_i,Y_i)$ に置かれています。

高橋君は $1$ 回の移動において、上下左右いずれかの方向を選んで、障害物に当たるまで進み続けます。
障害物に当たるとその $1$ つ手前のマスで停止します。 なお、スケート場の周りは崖になっており、障害物に当たらないような移動は禁止とします。

高橋君ははじめ $(s_x,s_y)$ にいて、何回か移動することで $(g_x,g_y)$ で停止したいと考えています。

$(g_x,g_y)$ へ辿り着くには最小で何回の移動が必要ですか？辿り着けないときはその旨を伝えてください。

输入格式

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

$H$ $W$ $N$ $s_x$ $s_y$ $g_x$ $g_y$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_N$ $Y_N$

输出格式

$(g_x,g_y)$ へ辿り着くには最小で何回の移動が必要か出力せよ。
ただし、辿り着けないならば -1 と出力せよ。

题目大意

有一个溜冰场，由 $H$ 个横行和 $W$ 个纵列的网格表示。 $(i,j)$ 表示从上往下第 i 行和从 左往右第 $j$ 列的方格。 溜冰场上有 $N$ 个障碍物。第 $i$ 个障碍物位于 $(Xi ,Yi)$ 处。 在一次移动中，小高可以从上、下、左、右四个方向中选择一个，一直移动到碰到障碍 物为止。由于溜冰场四周都是悬崖峭壁，因此禁止他开始一个永远不会碰到障碍物的移动。 小高最初在 $(sx,sy)$ 处，他想停在$(gx ,gy)$ 处。找出移动到 $(gx,gy)$ 的最少移动次数，如果不 可能，请输出 $-1$。

This translation comes from highkj

7 8 7
3 4
5 6
1 4
2 1
2 8
4 5
5 7
6 2
6 6

4

4 6 2
3 2
3 5
4 5
2 5

-1

1 10 1
1 5
1 1
1 7

-1

提示

制約

• $1\leq\ H\ \leq\ 10^9$
• $1\leq\ W\ \leq\ 10^9$
• $1\leq\ N\ \leq\ 10^5$
• $1\leq\ s_x,g_x\leq\ H$
• $1\leq\ s_y,g_y\leq\ W$
• $1\leq\ X_i\ \leq\ H$
• $1\leq\ Y_i\ \leq\ W$
• $(s_x,s_y)\neq\ (g_x,g_y)$
• $(s_x,s_y)\neq\ (X_i,Y_i)$
• $(g_x,g_y)\neq\ (X_i,Y_i)$
• $i\neq\ j$ ならば、$(X_i,Y_i)\neq\ (X_j,Y_j)$
• 入力は全て整数である

Sample Explanation 1

 図は、$(s_x,s_y)$ を S で、$(g_x,g_y)$ を G で表しています。 $ (3,4)\rightarrow(2,4)\ \rightarrow(2,2)\ \rightarrow(5,2)\ \rightarrow(5,6) $ と移動すると、$4$ 回の移動で $(g_x,g_y)$ に辿り着くことができます。

Sample Explanation 2

 $(g_x,g_y)$ で停止する必要があります。 通過しただけでは $(g_x,g_y)$ へ辿り着いたとみなされないことに注意してください。

Sample Explanation 3

 左を選んで進むと、高橋君は $(g_x,g_y)$ を通過したのちに崖に落ちてしまいます。 スケート場の周りは崖になっており、障害物に当たらないような移動は禁止されていることに注意してください。