问题描述

有一个用网格表示的溜冰场，其中有$H$行和$W$列。记$(i, j)$为从上往下数第$i$行，从左往右数第$j$列的方格。

溜冰场上有$N$个障碍物。第$i$个障碍物位于$(X_i,Y_i)$处。

在一次移动中，高桥选择上、下、左、右四个方向之一并继续移动，直到撞到一个障碍物为止。当他撞到障碍物时，他停在障碍物前面的方格上。由于溜冰场被悬崖围绕，禁止开始一次移动且永远不会撞到障碍物。

高桥最初位于$(s_x,s_y)$处。他想要进行一些移动以停在$(g_x,g_y)$处。

找出达到$(g_x,g_y)$所需的最小移动次数。如果不可能达到，则报告该事实。

约束条件

• $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)$。
• 输入中的所有值都是整数。

输入

输入格式如下，从标准输入读入：

$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。

示例输入1

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

示例输出1

4

在图中，$(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)$。

示例输入2

4 6 2
3 2
3 5
4 5
2 5

示例输出2

-1

他必须停在$(g_x,g_y)$处。
注意，只是通过$(g_x,g_y)$并不被认为是达到目标。

示例输入3

1 10 1
1 5
1 1
1 7

示例输出3

-1

如果他选择向左移动，高桥会在通过$(g_x,g_y)$后掉下悬崖。
请注意，由于溜冰场被悬崖围绕，禁止开始一次移动且永远不会撞到障碍物。