1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <algorithm>  5 #include <cmath>  6   7 using namespace std;  8   9 const int inf=8500000; 10 const int MAXN=1050; 11 const int MAXM=20000000; 12 int s1_s2,dis1[MAXN],dis2[MAXN],head[MAXN],dfn[MAXN],low[MAXN],belong[MAXN]; 13 int st[MAXN],stop,indx,tot,pat; 14 bool stack[MAXN]; int leng; 15 int n,hn,ln; 16 struct d{ 17     int x,y; 18 }point[MAXN],s1,s2; 19 struct h{ 20     int u,v; 21 }hate[MAXN*2]; 22 struct l{ 23     int u,v; 24 }like[MAXN*2]; 25  26 struct ei{ 27     int u,v; 28     int next; 29 }edge[MAXM]; 30  31 void addedge(int u,int v){ 32     edge[tot].u=u; 33     edge[tot].v=v; 34     edge[tot].next=head[u]; 35     head[u]=tot++; 36 } 37  38 void tarjan(int u){ 39     int v; 40     dfn[u]=low[u]=++indx; 41     st[stop++]=u; 42     stack[u]=true; 43     for(int e=head[u];e!=-1;e=edge[e].next){ 44         v=edge[e].v; 45         if(dfn[v]==0){ 46             tarjan(v); 47             low[u]=min(low[u],low[v]); 48         } 49         else if(stack[v]){ 50             low[u]=min(low[u],dfn[v]); 51         } 52     } 53     if(dfn[u]==low[u]){ 54         pat++; 55         do{ 56             v=st[--stop]; 57             stack[v]=false; 58             belong[v]=pat; 59         }while(u!=v); 60     } 61 } 62  63 bool slove(){ 64     int u,v; 65      66     memset(head,-1,sizeof(head)); 67     memset(dfn,0,sizeof(dfn)); 68     memset(low,0,sizeof(low)); 69     memset(belong,0,sizeof(belong)); 70     stop=0; indx=0; tot=0; pat=0; 71     memset(stack,false,sizeof(stack)); 72      73      74     for(int i=0;i<hn;i++){ 75         u=hate[i].u; 76         v=hate[i].v; 77         addedge(u*2,v*2+1); 78         addedge(v*2,u*2+1); 79         addedge(2*u+1,2*v); 80         addedge(2*v+1,2*u); 81     } 82     for(int i=0;i<ln;i++){ 83         u=like[i].u; 84         v=like[i].v; 85         addedge(u*2,v*2); 86         addedge(v*2,u*2); 87         addedge(2*u+1,2*v+1); 88         addedge(2*v+1,2*u+1); 89     } 90     for(int i=0;i<n;i++){ 91         for(int j=i+1;j<n;j++){ 92             if(dis1[i]+dis1[j]>leng){ 93                 addedge(i*2,j*2+1); 94                 addedge(j*2,i*2+1); 95             } 96             if(dis2[i]+dis2[j]>leng){ 97                 addedge(i*2+1,j*2); 98                 addedge(j*2+1,i*2); 99             }100             if(dis1[i]+s1_s2+dis2[j]>leng){101                 addedge(i*2,j*2);102                 addedge(j*2+1,i*2+1);103             }104             if(dis2[i]+s1_s2+dis1[j]>leng){105                 addedge(j*2,i*2);106                 addedge(i*2+1,j*2+1);107             }108         }109     }110     for(int i=0;i<2*n;i++){111         if(dfn[i]==0)112         tarjan(i);113     }114     bool flag=true;115     for(int i=0;i<n;i++){116         if(belong[2*i]==belong[2*i+1]){117             flag=false;118             break;119         }120     }121     return flag;122 }123 124 int main(){125     int u,v; int tmp;126     while(scanf("%d%d%d",&n,&hn,&ln)!=EOF){127         scanf("%d%d%d%d",&s1.x,&s1.y,&s2.x,&s2.y);128         for(int i=0;i<n;i++){129         scanf("%d%d",&point[i].x,&point[i].y);130         }131         for(int i=0;i<hn;i++){132             scanf("%d%d",&u,&v);133             u--; v--;134             hate[i].u=u; hate[i].v=v;135         }136         for(int i=0;i<ln;i++){137             scanf("%d%d",&u,&v);138             u--; v--; 139             like[i].u=u; like[i].v=v;140         }141         for(int i=0;i<n;i++){142             tmp=abs(point[i].x-s1.x)+abs(point[i].y-s1.y);143             dis1[i]=tmp;144             tmp=abs(point[i].x-s2.x)+abs(point[i].y-s2.y);145             dis2[i]=tmp;146         }147         s1_s2=abs(s1.x-s2.x)+abs(s1.y-s2.y);148         int lown=1,high=inf,ans=-1;149         while(lown<=high){150             int mid=(lown+high)/2;151             leng=mid;152             if(slove()){153                 ans=mid;154                 high=mid-1;155             }156             else lown=mid+1;157         }158         printf("%d\n",ans);159     }160     return 0;161 }