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 <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <utility>
#include <vector>
 
using namespace std;
 
using P = pair<int, int>; // (dist, node's id)
using PPI = pair<P, int>;
 
const int inf = 1 << 28;
 
int N, A, B, C;
 
P cost[3][20000];
vector<int> G[20000];
int old_id[20000];
 
void dijkstra(int s) {
    for (int v = 0; v < N; v++) {
        cost[s][v] = {inf, inf};
    }
 
  cost[s][s] = {0, old_id[s]};
 
  priority_queue<PPI, vector<PPI>, greater<PPI>> Q;
  Q.push({{0, old_id[s]}, s});
  while (!Q.empty()) {
        auto q = Q.top();
        Q.pop();
        P val = q.first;
        int v = q.second;
    
        if (cost[s][v] < val) continue;
 
        for (int to : G[v]) {
            P nval = make_pair(val.first + 1, min(val.second, old_id[to]));
            if (cost[s][to] > nval) {
                cost[s][to] = nval;
                Q.push({nval, to});
            }
        }
    }
}
 
int main() {
  cin >> N >> A >> B >> C;
 
  int mina = inf, minb = inf, minc = inf;
 
  static int group[20000];
  memset(group, -1, sizeof(group));
  for (int i = 0; i < A; i++) {
    int a;
    cin >> a;
    a--;
    group[a] = 0;
 
    mina = min(mina, a);
  }
  for (int i = 0; i < B; i++) {
    int b;
    cin >> b;
    b--;
    group[b] = 1;
 
    minb = min(minb, b);
  }
  for (int i = 0; i < C; i++) {
    int c;
    cin >> c;
    c--;
    group[c] = 2;
 
    minc = min(minc, c);
  }
  map<int, int> mp;
  int id = 3;
 
  old_id[0] = mina;
  old_id[1] = minb;
  old_id[2] = minc;
 
  for (int v = 0; v < N; v++) {
    if (0 <= group[v] and group[v] < 3)
      mp[v] = group[v];
    else {
      mp[v] = id++;
      old_id[mp[v]] = v;
    }
}
  // static bool state[3][3];
 
  int M;
  cin >> M;
  for (int i = 0; i < M; i++) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
 
    G[mp[x]].emplace_back(mp[y]);
    G[mp[y]].emplace_back(mp[x]);
 
    /*
    if (mp[x] < 3 and mp[y] < 3) {
      state[mp[x]][mp[y]] = state[mp[y]][mp[x]] = true;
    }
    */
  }
 
  // (1) 3 group is connected
  // state[0][0] = state[1][1] = state[2][2] = true;
  /*
  for (int r = 0; r < 3; r++) {
    int cnt = 0;
    for (int c = 0; c < 3; c++) {
      cnt += state[r][c];
    }
    if (cnt == 3) {
      cout << 2 << " " << min({mina, minb, minc}) + 1 << endl;
      return 0;
    }
}
*/
  // (2) 2 group is connected
  /*
  int g1 = -1, g2 = -1;
  for (int r = 0; r < 3; r++) {
    for (int c = 0; c < 3; c++) {
      if (r != c and state[r][c]) {
        g2 = c;
        break;
      }
    }
    if (g2 >= 0) {
      g1 = r;
      break;
    }
}
*/
  // Dijkstra
    for (int s = 0; s < 3; s++) {
        dijkstra(s);
    }
 
    P score = {inf, inf};
    for (int v = 0; v < id; v++) {
        score =
            min(score,
                {cost[0][v].first + cost[1][v].first + cost[2][v].first,
                min({cost[0][v].second, cost[1][v].second, cost[2][v].second})});
    }
    cout << score.first << " " << score.second + 1 << endl;

    return 0;
}