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>
using namespace std;
struct edge{int to,cost;};
typedef pair<int,int> P;
#define MAX_N 100005

int N,M,A[3];
vector< edge > G[MAX_N];
int D[(1<<3)][MAX_N];

void dijkstra(int bit,int* d){
  for(int i=0;i<MAX_N;i++)d[i]=1e9;
  priority_queue< P , vector<P> , greater<P> > Q;

  if( __builtin_popcount(bit) == 1){
    for(int i=0;i<3;i++){
      if(bit>>i&1){
        Q.push(P(0,N+i));
        d[N+i]=0;
      }
    }
  }else{
    for(int i=0;i<N+3;i++){
      d[i]=0;
      for(int j=0;j<3;j++){
        if(bit>>j&1){
          d[i]+=D[(1<<j)][i];
        }
      }
      Q.push(P(d[i],i));
    }
  }
  
  while(!Q.empty()){
    P p=Q.top();Q.pop();
    int pos=p.second;
    int cost=p.first;
    if(d[pos]<cost)continue;
    for(int i=0;i<(int)G[pos].size();i++){
      edge e=G[pos][i];
      if(cost+e.cost<d[e.to]){
        d[e.to]=cost+e.cost;
        Q.push(P(d[e.to],e.to));
      }
    }
  }
}

int main(){
  scanf("%d",&N);
  for(int k=0;k<3;k++)scanf("%d",&A[k]);
  for(int k=0;k<3;k++){
    for(int i=0;i<A[k];i++){
      int id;
      scanf("%d",&id);
      id--;
      G[N+k].push_back( (edge){id,0} );
      G[id].push_back( (edge){N+k,0} );
    }
  }
  scanf("%d",&M);
  for(int i=0;i<M;i++){
    int a,b;
    scanf("%d %d",&a,&b);
    a--,b--;
    G[a].push_back((edge){b,1});
    G[b].push_back((edge){a,1});
  }
  
  for(int k=1;k<(1<<3);k++)dijkstra(k,D[k]);
  int ans=1e9,ans2=-1;
  
  for(int i=0;i<N;i++){
    for(int j=0;j<(1<<3);j++){
      int k=(1<<3)-1-j;
      int cost=D[j][i]+D[k][i];
      if(ans>cost){
        ans=cost;
        ans2=i;
      }
    }
  }

  printf("%d %d\n",ans,ans2+1);
  return 0;
}