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 <cstdio>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>

using namespace std;

#define SIZE 10000
#define INF 1000000000

vector<int> G[SIZE];

vector<pair<int,int> > dijkstra(int n, int start) {
  priority_queue<pair<pair<int,int>, int>> pq;
  bool visited[SIZE] = {};
  vector<pair<int,int> > res(n, {INF, INF});

  pq.push({{0, -start}, start});

  while(pq.size()) {
    auto p = pq.top();
    pq.pop();

    int now = p.second;
    int len = -p.first.first;
    int minV = -p.first.second;

    if (visited[now]) continue;
    visited[now] = true;
    res[now] = {len, minV};

    for (int to : G[now]) {
      pq.push({{-len-1, -min(minV, to)}, to});
    }
  }

  return res;
}

int main() {
  int N, M, A, B, C, x;
  vector<int> a, b, c;
  int root[SIZE];

  scanf("%d%d%d%d", &N, &A, &B, &C);

  for (int i=0; i<A; i++) {
    scanf("%d", &x);
    a.push_back(x-1);
  }

  for (int i=0; i<B; i++) {
    scanf("%d", &x);
    b.push_back(x-1);
  }

  for (int i=0; i<C; i++) {
    scanf("%d", &x);
    c.push_back(x-1);
  }

  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  sort(c.begin(), c.end());

  for (int i=0; i<N; i++) root[i] = i;
  for (int x : a) root[x] = a[0];
  for (int x : b) root[x] = b[0];
  for (int x : c) root[x] = c[0];

  scanf("%d", &M);

  for (int i=0; i<M; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    x--; y--;

    G[root[x]].push_back(root[y]);
    G[root[y]].push_back(root[x]);
  }

  auto vecA = dijkstra(N, root[a[0]]);
  auto vecB = dijkstra(N, root[b[0]]);
  auto vecC = dijkstra(N, root[c[0]]);

  pair<int,int> ans = {INF, -1};

  for(int i=0; i<N; i++) {
    if (i != root[i]) continue;

    int len = vecA[i].first + vecB[i].first + vecC[i].first;
    int minV = min({vecA[i].second, vecB[i].second, vecC[i].second});

    ans = min(ans, {len, minV});
  }

  cout << ans.first << " " << ans.second + 1 << endl;

  return 0;
}