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>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 10010;

struct edge {
    int v;
    ll w;
    edge() {}
    edge(int v, ll w) : v(v), w(w) {};
};

vector<pii> dijkstra(int n, vector<vector<edge> >& G, int s) {
    vector<pii> d(n, pii(MAXN, MAXN)); d[s] = pii(0, s);
    priority_queue<pair<pii, int>, vector<pair<pii, int> >, greater<pair<pii, int> > > que;
    que.push(make_pair(d[s], s));
    while (!que.empty()) {
        auto p = que.top(); que.pop();
        int u = p.second;
        pii dist = p.first;
        if (dist > d[u]) continue;
        for (edge e : G[u]) {
            if (d[e.v] > pii(d[u].first+e.w, min(d[u].second, e.v))) {
                d[e.v] = pii(d[u].first+e.w, min(d[u].second, e.v));
                que.push(make_pair(d[e.v], e.v));
            }
        }
    }
    return d;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, A, B, C;
    cin >> N >> A >> B >> C;
    vector<vector<edge> > G(N+3);
    for (int i = 0; i < A; i++) {
        int a;
        cin >> a;
        a--;
        G[a].emplace_back(N, 0);
        G[N].emplace_back(a, 0);
    }
    for (int i = 0; i < B; i++) {
        int a;
        cin >> a;
        a--;
        G[a].emplace_back(N+1, 0);
        G[N+1].emplace_back(a, 0);
    }
    for (int i = 0; i < C; i++) {
        int a;
        cin >> a;
        a--;
        G[a].emplace_back(N+2, 0);
        G[N+2].emplace_back(a, 0);
    }
    int M;
    cin >> M;
    for (int i = 0; i < M; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        G[x].emplace_back(y, 1);
        G[y].emplace_back(x, 1);
    }
    vector<vector<pii> > d(3);
    for (int i = 0; i < 3; i++) d[i] = dijkstra(N+3, G, N+i);
    pii ans(MAXN, MAXN);
    for (int i = 0; i < N; i++) {
        pii tmp;
        tmp.second = MAXN;
        for (int j = 0; j < 3; j++) {
            tmp.first += d[j][i].first;
            tmp.second = min(tmp.second, d[j][i].second);
        }
        ans = min(ans, tmp);
    }
    cout << ans.first << " " << ans.second+1 << endl;
    return 0;
}