二师兄的纪录片[2020海淀区智慧杯普及组T4]

题目描述

二师兄护送师傅取经成功之后，成了名人，他决定重新把取经的路再走一遍， 并且拍摄一部纪录片宣传路上的风光。

从东土大唐到天竺的地图，是正方形的，城市坐落在 N 行 N 列的方形地图上。 地图从位置(1，1)排列到位置(N，N)。地图上每一个格子是一座城市， 上下左右直接相邻的城市之间可以一天到达。

有 P 座城市住着野蛮人(野蛮城市)，他们只吃红烧肉。一天三顿红烧肉， 连早餐都吃红烧肉。二师兄是出家人，决定不去这些城市。

另有 Q 座城市(友好城市)希望二师兄帮他们多宣传城市风光，所以给二师 兄提供一个优惠条件:如果二师兄在这座城市(X)停留三天，就可以在第四天派专机把二师兄送到另外一座城市 Y。从城市 X 飞到城市 Y 可以瞬间完成，即:二师兄在到达 X 城市后，可以选择四天后到达 Y 城市。当然，二师兄也可以选择只在 X 城市停留一天，然后访问 X 城市直接相邻的城市。

已知长安城位于地图的(1，1)位置，目的地灵山位于地图的(N，N)位置。 每一个友好城市只能直飞到另外一个城市。

请求出二师兄从长安到达灵山最少需要多少天。

输入格式

输入数据第一行有三个整数，分别是 N，P，Q。整数之间用空格分开。 城市坐标系 X 轴向下，起点为 1，Y 轴向右，起点为 1。

数据接下来的 P 行，每行两个整数 a,b，代表某一个野蛮城市的坐标(a,b)。 位置信息(a,b)表示在 X-Y 坐标系中的位置。

再接下来的 Q 行，每行四个整数，代表友好城市 X 的坐标和从 X 能直飞的城市 Y 的坐标。

输出格式

输出数据一行，表示二师兄从长安去往灵山最少需要多少天。 如果从长安到达不了灵山，则输出-1。

二师兄在长安出发那天记为第 1 天，到达灵山那天的日期就是输出数据。

样例 #1

样例输入 #1

5 7 0
1 2
2 4
3 2
3 4
4 2
4 4
5 4

样例输出 #1

11

样例 #2

样例输入 #2

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

样例输出 #2

12

提示

样例1解释：

样例数据后面的解释说明当中，“.”代表可以访问的普通城市，“#”代表野蛮城市。“1”代表 X 城市和能从“1”直飞的城市 Y。

原地图:

. # . . .
. . . # .
. # . # .
. # . # .
. . . # .

到达目的地的走法:

1 # 5 6 7
2 3 4 # 8
. # . # 9
. # . # 10
. . . # 11

样例2解释：

样例数据后面的解释说明当中，“.”代表可以访问的普通城市，“#”代表野蛮城市。“1”代表 X 城市和能从“1”直飞的城市 Y。

原地图：

. # . . . # . . .
. . . # . # . # .
. # . # . # . # .
. # . # . # . # .
. . . # . # . # .
. 1 . # . # . # .
. . . # . # . # .
. . . # . # . # 1
. . . # . . . # .

走法说明: 走到 6 2 点的时候，穿越到 8 9 点。

1 # . . . # . . .
2 . . # . # . # .
3 # . # . # . # .
4 # . # . # . # .
5 . . # . # . # .
6 7 . # . # . # .
. . . # . # . # .
. . . # . # . # 11
. . . # . . . # 12

数据范围：

对于 30% 数据，Q=0，2 ≤ N ≤ 10

对于 60% 数据，Q=0，2 ≤ N ≤ 100

对于 100% 数据, 0 ≤ P ≤ 10000, 0 ≤ Q ≤ 100, 2 ≤ N ≤ 100

数据保证(1，1)和(N，N)既不是友好城市，也不是野蛮市。