该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

潮阳实验学校初中部冬令营趣闻四 —— 旅行记录

题目描述

潮阳实验学校初中部计划在夏令营（对，是夏令营）组织一场重走西游取经路。学校选派姚老师在寒假期间去旅行并记录相关信息。

从东土大唐到天竺的地图，是正方形的，城市坐落在 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

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

说明/提示

对于 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）既不是友好城市，也不是野蛮城市。

样例1解释：