滑冰

题目描述

有一个用 $H$ 行 $W$ 列网格表示的滑冰场。用 $(i, j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的格子。

滑冰场中有 $N$ 个障碍物。第 $i$ 个障碍物位于 $(X_i,Y_i)$。

在一次移动中,高桥选择上、下、左、右四个方向之一,并一直移动直到撞上障碍物。

撞上障碍物时,他停在障碍物正前方的一格。 由于滑冰场四周是悬崖,不允许开始一次永远不会撞到障碍物的移动。

高桥最初在 $(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
⋮
X_N Y_N

输出格式

输出停在 $(g_x,g_y)$ 所需的最少移动次数。

如果无法到达,输出 -1。

样例

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

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

4 6 2
3 2
3 5
4 5
2 5

-1

他必须停在 $(g_x,g_y)$。

注意,仅仅是从 $(g_x,g_y)$ 经过不算是到达目标。

1 10 1
1 5
1 1
1 7

-1

如果他选择向左移动,高桥在穿过 $(g_x,g_y)$ 后会掉下悬崖。

注意,由于滑冰场四周是悬崖,不允许开始一次永远不会撞到障碍物的移动。

数据范围

• $1 \le H \le 10^9$
• $1 \le W \le 10^9$
• $1 \le N \le 10^5$
• $1 \le s_x,g_x \le H$
• $1 \le s_y,g_y \le W$
• $1 \le X_i \le H$
• $1 \le Y_i \le 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)$。
• 输入中的所有值均为整数。