题目内容

某运营商需要在某一区城铺设光缆，起点为机房，终点为某小区，整个区域以一个$m*n$的矩阵表示，光缆沿着矩阵的边铺设(不允许走对角线)，区域内有些节点可以经过，但有些节点(如图红色$x$的位置,输入时给定) 因为各种因素无法经过，起点的机房与终点的小区可能在区域内的任何位置，计算从机房到目标小区铺设光缆的最短距离(如果光缆无法从起点机房铺设到达目标小区，返回$-1$)。

输入描述

$m$矩阵宽(横轴点数量，例如图示为$11$，以$0$~$10$作为下标)

$n$矩阵高(纵轴点数量，例如图示为$8$，以$0$~$7$作为下标)

机房坐标($a1,a2$)

目标小区坐标($b1,b2$)

矩阵内不允许经过的节点数量$k$

依次为这些不允许经过的节点坐标

$1<=m,n<=1000$

$0<=k<=100000$

输出描述

从机房到目标小区铺设光缆的最短距离

样例1

输入

11
8
2 3
7 5
6
2 4
3 5
4 4
5 4
6 4
7 4

输出

9

说明

$11*8$的矩阵(横轴坐标$0$~$10$，纵轴坐标$0$~$7$)

起始点(机房)为坐标($2\ 3$)

目标点(要连到的小区)为坐标($7\ 5$)

矩阵内不允许经过的节点数为$6$个

依次给出这些不允许经过的节点坐标

样例2

输入

3
3 
0 0
2 2
3
0 1
1 1
2 1

输出

-1

说明

$3*3$的矩阵

起始点(机房)为坐标($0\ 0$)

目标点(要连到的小区)为坐标($2\ 2$)

矩阵内不允许经过的节点数为$3$个

依次给出这些不允许经过的节点坐标