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 INF (1e8)
#define N 10005
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> P1;
typedef pair<P,P> P2;

int n, ABC[3], grade[N], Min[3];
vector<int> G[N];

P d[N], d2[2][N];

void dijkstra(){
  
  priority_queue<P1,vector<P1>,greater<P1> > q;
  
  for(int i=0;i<N;i++) d[i]=P(INF,INF);

  d[n]=P(0,Min[0]);
  q.push(P1(P(0,Min[0]),n));
  
  while(!q.empty()){
    
    P1 t=q.top(); q.pop();
    
    int cost1=t.first.first;
    int cost2=t.first.second;
    int node=t.second;

    if(d[node]<P(cost1,cost2)) continue;

    for(int i=0;i<G[node].size();i++){
      
      int nnode=G[node][i];
      int ncost1=cost1+1;
      int ncost2=min(cost2,nnode);
      
      if(nnode>=n) ncost2=min(ncost2,Min[nnode-n]);
      
      if(d[nnode]>P(ncost1,ncost2)){
	d[nnode]=P(ncost1,ncost2);
	q.push(P1(P(ncost1,ncost2),nnode));
      }
    }
    
  }
  
}

P dijkstra2(){
  
  P res=P(INF,INF);

  priority_queue<P2,vector<P2>,greater<P2> > q;

  for(int i=0;i<2;i++)
    for(int j=0;j<N;j++) d2[i][j]=P(INF,INF);
  
  d2[0][n+1]=P(0,Min[1]);
  q.push(P2(P(0,Min[1]),P(0,n+1)));
  
  while(!q.empty()){

    P2 t=q.top(); q.pop();

    int cost1=t.first.first;
    int cost2=t.first.second;
    int idx=t.second.first;
    int node=t.second.second;
    
    if(d2[idx][node]<P(cost1,cost2)) continue;
    if(idx==1&&node==n+2) res=min(res,P(cost1,cost2));
    
    for(int i=0;i<G[node].size();i++){
      
      int nnode=G[node][i];
      int ncost1=cost1+1;
      int ncost2=min(cost2,nnode);
      int nidx2=idx;
      
      if(nnode>=n) ncost2=min(ncost2,Min[nnode-n]);
      
      if(d2[nidx2][nnode]>P(ncost1,ncost2)){
	d2[nidx2][nnode]=P(ncost1,ncost2);
	q.push(P2(P(ncost1,ncost2),P(nidx2,nnode)));
      }
      
    }
    
    if(idx==0){
      
      idx=1;
      cost1=cost1+d[node].first;
      cost2=min(cost2,d[node].second);
      
      if(d2[idx][node]>P(cost1,cost2)){
	d2[idx][node]=P(cost1,cost2);
	q.push(P2(P(cost1,cost2),P(idx,node)));
      }
	
    }
    
  }
  
  return res;
}

int main(){
  
  cin>>n;

  for(int i=0;i<3;i++) cin>>ABC[i];
  
  memset(grade,-1,sizeof(grade));

  for(int i=0;i<3;i++){

    Min[i]=INF;
    
    for(int j=0;j<ABC[i];j++){
      int node;
      cin>>node;
      grade[node-1]=i;
      Min[i]=min(Min[i],node-1);
    }
    
  }
  
  int m;
  cin>>m;
  
  for(int i=0;i<m;i++){
    int x, y;
    cin>>x>>y;
    if(grade[x-1]!=-1) x=n+grade[x-1]+1;
    if(grade[y-1]!=-1) y=n+grade[y-1]+1;
    if(x==y) continue;
    G[x-1].push_back(y-1);
    G[y-1].push_back(x-1);
  }
  
  dijkstra();
  
  P ans=dijkstra2();
  
  cout<<ans.first<<' '<<ans.second+1<<endl;
  
  return 0;
}