Problem: Example

Input

4 2 1 1
1 2
3
4
3
1 2
2 4
3 4


Output

2 1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
typedef pair<P,int>P2;

int n,nA,nB,nC,x,y,m;
vector<P>v[100009];
vector<int> A,B,C;
set<int>sA,sB,sC;

P d1[100009];
P d2[100009];
P d3[100009];

void dij1(){
    priority_queue<P2,vector<P2>,greater<P2> >q;
    r(i,100009)d1[i]=P(1e8,1e8);
    q.push(P2(P(0,1e9),A[0]));
    d1[A[0]]=P(0,1e9);
    while(!q.empty()){
        P2 p=q.top();q.pop();
        P cost = p.first;
        int now = p.second;
        if(d1[now]<cost)continue;
        r(i,v[now].size()){
            P pp=v[now][i];
            int nex=pp.first;
            P co=P(pp.second+cost.first,min(cost.second,nex));
            if(d1[nex]<=co)continue;
            d1[nex]=co;
            q.push(P2(co,nex));
        }
    }
}

void dij2(){
    priority_queue<P2,vector<P2>,greater<P2> >q;
    r(i,100009)d2[i]=P(1e8,1e8);
    q.push(P2(P(0,1e9),B[0]));
    d2[B[0]]=P(0,1e9);
    while(!q.empty()){
        P2 p=q.top();q.pop();
        P cost = p.first;
        int now = p.second;
        if(d2[now]<cost)continue;
        r(i,v[now].size()){
            P pp=v[now][i];
            int nex=pp.first;
            P co=P(pp.second+cost.first,min(cost.second,nex));
            if(d2[nex]<=co)continue;
            d2[nex]=co;
            q.push(P2(co,nex));
        }
    }
}
void dij3(){
    priority_queue<P2,vector<P2>,greater<P2> >q;
    r(i,100009)d3[i]=P(1e8,1e8);
    q.push(P2(P(0,1e9),C[0]));
    d3[C[0]]=P(0,1e9);
    while(!q.empty()){
        P2 p=q.top();q.pop();
        P cost = p.first;
        int now = p.second;
        if(d3[now]<cost)continue;
        r(i,v[now].size()){
            P pp=v[now][i];
            int nex=pp.first;
            P co=P(pp.second+cost.first,min(cost.second,nex));
            if(d3[nex]<=co)continue;
            d3[nex]=co;
            q.push(P2(co,nex));
        }
    }
}


signed main(){
    cin>>n>>nA>>nB>>nC;
    r(i,nA){
        cin>>x; x--;
        A.push_back(x);
        sA.insert(x);
        v[n].push_back(P(x,0));
        v[x].push_back(P(n,0));
    }
    r(i,nB){
        cin>>x; x--;
        B.push_back(x);
        sB.insert(x);
        v[n+1].push_back(P(x,0));
        v[x].push_back(P(n+1,0));
    }
    r(i,nC){
        cin>>x; x--;
        C.push_back(x);
        sC.insert(x);
        v[n+2].push_back(P(x,0));
        v[x].push_back(P(n+2,0));
    }
    cin>>m;
    r(i,m){
        cin>>x>>y; x--; y--;
        v[x].push_back(P(y,1));
        v[y].push_back(P(x,1));
    }

    dij1();
    dij2();
    dij3();

    P ans=P(1e9,1e9);

    r(i,n){
        P tmp=P(0,i);
        r(j,3){
            int MIN=1e9;
            if(j==0)MIN=min(MIN,d1[i].first) , tmp.second=min(tmp.second,d1[i].second);
            if(j==1)MIN=min(MIN,d2[i].first) , tmp.second=min(tmp.second,d2[i].second);
            if(j==2)MIN=min(MIN,d3[i].first) , tmp.second=min(tmp.second,d3[i].second);
            tmp.first+=MIN;
        }
        ans=min(ans,tmp);
    }
    cout<<ans.first<<' '<<ans.second+1<<endl;

}