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 rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef pair<int,int> pii;

const int INF = 1e9;

int main(){
  int n; cin >> n;
  vector< vector<pii> > g(n);

  vector<int> sizes(3);
  rep(i,3)cin >> sizes[i];

  vector< vector<int> > friends(3);
  rep(i,3){
    friends[i].resize(sizes[i]);
    rep(j,sizes[i]){
      cin >> friends[i][j]; friends[i][j]--;
      if(j){
	g[friends[i][j-1]].push_back(pii(0,friends[i][j]));
	g[friends[i][j]].push_back(pii(0,friends[i][j-1]));
      }
    }
  }
  
  int m; cin >> m;
  rep(i,m){
    int a,b; cin >> a >> b; a--; b--;
    g[a].push_back(pii(1,b));
    g[b].push_back(pii(1,a));
  }

  vector< vector<pii> > d(3, vector<pii>(n, pii(INF,INF)));
  deque<int> q;
  rep(x,3){
    d[x][friends[x][0]] = pii(0, friends[x][0]);
    q.push_back(friends[x][0]);

    while(q.size()){
      int v = q.front(); q.pop_front();

      for(pii e : g[v]){
	int w = e.first, u = e.second;
	pii nxt = pii(d[x][v].first+w, min(d[x][v].second, u));
	if(d[x][u] > nxt){
	  d[x][u] = nxt;
	  if(w == 0) q.push_front(u);
	  else q.push_back(u);
	}
      }
    }
  }

  pii ans = pii(INF,INF);
  rep(i,n){
    int sum = 0, id = INF;
    rep(x,3){
      sum += d[x][i].first;
      id = min(id, d[x][i].second);
    }
    ans = min(ans, pii(sum,id));
  }
  cout << ans.first << " " << ans.second+1 << endl;
}