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 int long long
#define N 10010
using namespace std;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}

vector<int> g[N],G[N];
int n;
set<int> A,B,C;

void input(){
  int a,b,c;
 
  cin>>n>>a>>b>>c;
  for(int i=0,t;i<a;i++) cin>>t,A.insert(t-1);
  for(int i=0,t;i<b;i++) cin>>t,B.insert(t-1);
  for(int i=0,t;i<c;i++) cin>>t,C.insert(t-1);

  int par[N];
  for(int i=0;i<N;i++) par[i] = i;
  for(int v:A) par[v] = *A.begin();
  for(int v:B) par[v] = *B.begin();
  for(int v:C) par[v] = *C.begin();
  
  int m;
  cin>>m;
  for(int i=0;i<m;i++){
    int u,v;
    cin>>u>>v; u--,v--;
    G[u].push_back(v);
    G[v].push_back(u);
    u = par[u], v = par[v];
    if(u == v) continue;
    g[u].push_back(v);
    g[v].push_back(u);
  }
}

typedef pair<int,int> P;
typedef pair<P,int> PP;
vector<P> dijkstra(int start){
  vector<P> D(N,P(INF,INF));
  priority_queue<PP,vector<PP>,greater<PP>> Q;

  Q.push(PP(P(0,start),start));
  D[start] = P(0,start);
  while(!Q.empty()){
    PP t = Q.top();Q.pop();
    P cost = t.first;
    int pos = t.second;
    if(D[pos] < cost)continue;

    for(int npos:g[pos]){
      P ncost = P(cost.first+1,min(cost.second,npos));
      if(D[npos] <= ncost) continue;
      Q.push(PP(ncost,npos));
      D[npos] = ncost;
    }
  }
  return D;
}

P calc(P a,P b,P c){
  int cost = a.first + b.first + c.first;
  int node = min(a.second,min(b.second,c.second));
  return P(cost,node);
}

signed main(){
  input();
  int a = *A.begin();
  int b = *B.begin();
  int c = *C.begin();
  vector<P> AD = dijkstra(a);
  vector<P> BD = dijkstra(b);
  vector<P> CD = dijkstra(c);
  
  P ans = P(INF,INF);
  for(int i=0;i<n;i++) Min(ans,calc(AD[i],BD[i],CD[i]));
  cout<<ans.first<<" "<<ans.second+1<<endl;
  return 0;
}