题目描述

有一个滑冰场，它可以视作一个 $H$ 行 $W$ 列的网格。令 $(i, j)$ 表示从上往下数第 $i$ 行，从左往右数第 $j$ 列的格子。 滑冰场上有 $N$ 个障碍物，第 $i$ 个障碍物在格子 $(X_i, Y_i)$ 里。 高桥在这个滑冰场上滑冰。每次滑冰，他从上、下、左、右四个方向中选择一个，向那个方向滑行，直到撞上障碍物。 撞上障碍物时，他会停在障碍物前面那个格子里。由于滑冰场四周是悬崖，滑冰时不能向不会撞上障碍物的方向滑行。 高桥最初在格子 $(s_x, s_y)$ 里。他想要在滑冰几次之后停在格子 $(g_x, g_y)$ 里。 求所需的最少滑冰次数。 若不可能做到，输出 -1。 限制 $1≤H≤10^9$ $1≤W≤10^9$ $1≤N≤10^5$ $1≤s_x ,g_x ≤H$ $1≤s_y ,g_y ≤W$ $1≤X_i ≤H$ $1≤Y_i ≤W$ $(s_x ,s_y) \ne (g_x ,g_y )$ $(s_x ,s_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$

输出格式

输出答案。

7 8 7

3 4

5 6

1 4

2 1

2 8

4 5

5 7

6 2

6 6

	样例一图示