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;
#define int long long
#define MAX 114514
vector<int> G[MAX];
int dpA[MAX],dpB[MAX],dpC[MAX];
bool used[MAX];
signed main(){
  int N,A,B,C;
  cin>>N>>A>>B>>C;
  int a[A],b[B],c[C];
  for(int i=0;i<A;i++) cin>>a[i];
  for(int i=0;i<B;i++) cin>>b[i];
  for(int i=0;i<C;i++) cin>>c[i];
  int M;
  cin>>M;
  int x[M],y[M];
  for(int i=0;i<M;i++) cin>>x[i]>>y[i];
  int ia=N,ib=N+1,ic=N+2;
  N+=3;
  set<int> sa,sb,sc;
  for(int i=0;i<A;i++){
    a[i]--;
    sa.insert(a[i]);
  }
  for(int i=0;i<B;i++){
    b[i]--;
    sb.insert(b[i]);
  }
  for(int i=0;i<C;i++){
    c[i]--;
    sc.insert(c[i]);
  }
  for(int i=0;i<M;i++){
    x[i]--;y[i]--;
    //cout<<x[i]<<":"<<y[i]<<endl;
    if(sa.count(x[i])) x[i]=ia;
    if(sb.count(x[i])) x[i]=ib;
    if(sc.count(x[i])) x[i]=ic;
    if(sa.count(y[i])) y[i]=ia;
    if(sb.count(y[i])) y[i]=ib;
    if(sc.count(y[i])) y[i]=ic;
    //cout<<x[i]<<":"<<y[i]<<endl;
    G[x[i]].push_back(y[i]);
    G[y[i]].push_back(x[i]);
  }
  memset(dpA,-1,sizeof(dpA));
  memset(dpB,-1,sizeof(dpB));
  memset(dpC,-1,sizeof(dpC));
  dpA[ia]=dpB[ib]=dpC[ic]=0;
  queue<int> q;
  q.push(ia);
  while(!q.empty()){
    int p=q.front();q.pop();
    for(int u:G[p]){
      if(dpA[u]<0){
	dpA[u]=dpA[p]+1;
	q.push(u);
      }
    }
  }
  q.push(ib);
  while(!q.empty()){
    int p=q.front();q.pop();
    for(int u:G[p]){
      if(dpB[u]<0){
	dpB[u]=dpB[p]+1;
	q.push(u);
      }
    }
  }
  q.push(ic);
  while(!q.empty()){
    int p=q.front();q.pop();
    for(int u:G[p]){
      if(dpC[u]<0){
	dpC[u]=dpC[p]+1;
	q.push(u);
      }
    }
  }
  int cost=1LL<<55LL;
  for(int i=0;i<N;i++){
    //cout<<i<<":"<<dpA[i]<<":"<<dpB[i]<<":"<<dpC[i]<<endl;
    if(sa.count(i)) continue;
    if(sb.count(i)) continue;
    if(sc.count(i)) continue;
    if(dpA[i]<0||dpB[i]<0||dpC[i]<0) continue;
    cost=min(cost,dpA[i]+dpB[i]+dpC[i]);
  }
  typedef pair<int,int> P;
  priority_queue<P> qa,qb,qc;
  
  set<int> ans;
  for(int i=0;i<N;i++){
    if(sa.count(i)) continue;
    if(sb.count(i)) continue;
    if(sc.count(i)) continue;
    if(dpA[i]<0||dpB[i]<0||dpC[i]<0) continue;
    if(cost==dpA[i]+dpB[i]+dpC[i]){
      qa.push(P(dpA[i],i));
      qb.push(P(dpB[i],i));
      qc.push(P(dpC[i],i));
    }
  }
  memset(used,0,sizeof(used));
  while(!qa.empty()){
    P p=qa.top();qa.pop();
    int d=p.first,v=p.second;
    //cout<<d<<":"<<v<<":"<<dpA[v]<<endl;
    if(used[v]) continue;
    used[v]=1;
    if(dpA[v]<=d) ans.insert(v);
    //cout<<d<<":"<<v<<":"<<dpA[v]<<endl;
    if(d==0) continue;
    //for(int u:G[v]) cout<<d-1<<":"<<u<<endl;
    for(int u:G[v]) qa.push(P(d-1,u));
  }
  
  memset(used,0,sizeof(used));
  while(!qb.empty()){
    P p=qb.top();qb.pop();
    int d=p.first,v=p.second;
    if(used[v]) continue;
    //cout<<d<<":"<<v<<":"<<dpB[v]<<endl;
    used[v]=1;
    if(dpB[v]<=d) ans.insert(v);
    if(d==0) continue;
    for(int u:G[v]) qb.push(P(d-1,u));
  }
  
  memset(used,0,sizeof(used));
  while(!qc.empty()){
    P p=qc.top();qc.pop();
    int d=p.first,v=p.second;
    if(used[v]) continue;
    //cout<<d<<":"<<v<<":"<<dpC[v]<<endl;
    used[v]=1;
    if(dpC[v]<=d) ans.insert(v);
    if(d==0) continue;
    for(int u:G[v]) qc.push(P(d-1,u));
  }
  if(ans.count(ia)) ans.insert(*sa.begin());
  if(ans.count(ib)) ans.insert(*sb.begin());
  if(ans.count(ic)) ans.insert(*sc.begin());

  //for(int i:ans) cout<<i<<" ";cout<<endl;
  
  cout<<cost<<" "<<*ans.begin()+1<<endl;
  return 0;
}