Documentary of the second senior brother

Title Description

After the second senior brother successfully escorted the master to learn lessons , Become a celebrity , He decided to take the road of learning again , And shoot a documentary to publicize the scenery on the road .

Map from Dongtu Datang to Tianzhu , It's Square , The city is located in N That's ok N Column on the square map . Map from location （1,1） Arrange to position （N,N）. Every grid on the map is a city , Up, down, left, right, and directly adjacent cities can be reached in one day .

Yes P Barbarians live in this city （ Savage City ）, They only eat braised meat . Three meals of braised meat a day , Even eat braised meat for breakfast . The second senior brother is a monk , Decide not to go to these cities .

have other Q city （ Friendly city ） I hope the second senior brother can help them publicize the city scenery more , So give the second senior brother a preferential condition ： If the second senior brother is in this city （X） Stay for three days , You can send a special plane to send the second brother to another city on the fourth day Y. From the city X Fly to the city Y It can be done in an instant , namely ： The second senior brother is arriving X After the city , You can choose to arrive in four days Y City . Of course , The second senior brother can also choose to only X Stay in the city for a day , And then visit X The city directly adjacent to the city .

Chang'an city is known to be located on the map （1,1） Location , The destination Lingshan is located on the （N,N） Location . Each sister city can only fly directly to another city .

Ask the second elder martial brother how many days it will take at least from Chang'an to Lingshan .

Input

The first row of input data has three integers , Namely N,P,Q.
Integers are separated by spaces . Urban coordinate system X Axis down , Starting from 1,Y Shaft to the right , Starting from 1.
Data next P That's ok , Two integers per line a,b, Coordinates representing a barbaric city (a,b).
Location information (a,b) It means that X-Y The position in the coordinate system .
And then the next Q That's ok , Four integers per line , On behalf of sister cities X Coordinates and from X Cities that can fly directly Y Coordinates of .

Output

Output data line , It means how many days it will take the second senior brother from Chang'an to Lingshan at least .
If you can't reach Lingshan from Chang'an , The output -1.
The second senior brother was recorded as the No. 1 on the day of departure in Chang'an 1 God , The date of arriving at Lingshan is the output data .

The sample input  Copy

【 Examples 1】
5 7 0
1 2
2 4
3 2
3 4
4 2
4 4
5 4
【 Examples 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

Sample output  Copy

【 Examples 1】
11
【 Examples 2】
12

Tips

Examples 1 Explain the sample data in the following explanation ,“.” Represents ordinary cities that can be visited ,“#” On behalf of barbaric cities .“1” representative X Cities and can be from “1” Cities that fly directly Y.

Original map ：
Examples 1 Original map .png

How to get to the destination ：


Examples 2 Explain the sample data in the following explanation ,“.” Represents ordinary cities that can be visited ,“#” On behalf of barbaric cities .“1” representative X Cities and can be from “1” Cities that fly directly Y.

Original map ：

Method description ： Go to the 6 2 A.m. , Cross to 8 9 spot .

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N=105;
struct node
{
    int x,y;
};
struct Q
{
    int x,y,step;
    friend bool operator < (Q a, Q b)
    {
        return a.step>b.step;// Note that the symbol here should be '>'
    }
};
vector<node>v[N][N];
bool maps[N][N];
bool vis[N][N];
priority_queue<Q>q;
int n,p,qq;
int dx[4]= {1,-1,0,0};
int dy[4]= {0,0,1,-1};
int bfs()
{
    while(q.size())
    {
        auto T=q.top();
        q.pop();
        if(vis[T.x][T.y]||T.x<1||T.x>n||T.y<1||T.y>n||maps[T.x][T.y]==1)    continue;
        if(T.x==n&&T.y==n)    return T.step;
        vis[T.x][T.y]=true;
        for(int i=0; i<4; i++)
        {
            q.push({T.x+dx[i],T.y+dy[i],T.step+1});
        }

        for(auto u:v[T.x][T.y])
        {
            q.push({u.x,u.y,T.step+4});
        }
    }
    return -1;
}
int main()
{
    cin>>n>>p>>qq;
    for(int i=1; i<=p; i++)
    {
        int x,y;
        cin>>x>>y;
        maps[x][y]=1;
    }
    for(int i=1; i<=qq; i++)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        v[x1][y1].push_back({x2,y2});
    }
    q.push({1,1,1});
    for(auto u:v[1][1])    q.push({1,1,4});
    cout<<bfs();
    return 0;
}