#1046. 二师兄的纪录片

二师兄的纪录片

题目描述

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

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

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

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

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

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

输入格式

输入数据第一行有三个整数,分别是 N,P,Q。
整数之间用空格分开。城市坐标系X轴向下,起点为1,Y 轴向右,起点为1。
数据接下来的 P 行,每行两个整数 a,b,代表某一个野蛮城市的坐标 (a,b)。
位置信息 (a,b) 表示在 X-Y 坐标系中的位置。
再接下来的 Q 行,每行四个整数,代表友好城市 X 的坐标和Y的坐标

输出格式

输出数据一行,表示二师兄从长安去往灵山最少需要多少天。
如果从长安到达不了灵山,则输出-1。
二师兄在长安出发那天记为第1天,到达灵山那天的日期就是输出数据。

5 7 0
1 2
2 4
3 2
3 4
4 2
4 4
5 4
11
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
12

提示

n100n \le100

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

到达目的地的走法:

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

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