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;
  // map<int, int> revmp;
  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;
    }
    // revmp[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);

  if (g1 >= 0) {
    int g3 = 3 - g1 - g2;

    P score = {inf, inf};
    for (int v = 0; v < id; v++) {
      P p = min(cost[g1][v], cost[g2][v]);
      score =
          min(score,
              {cost[g3][v].first + p.first, min(cost[g3][v].second, p.second)});
    }
    score.second = min({score.second, mina, minb, minc});

    cout << score.first + 1 << " " << score.second + 1 << endl;
  } else {
    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;
}