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>; // (ティツキツ敕ゥツ崢「テッツシツ古」ツδ妥」ツつケテ、ツクツ甘」ツ?ョテヲツ慊?・ツーツ湘ゥツ?づァツつケ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]; // テ・ツ、ツ嘉ヲツ渉崚・ツセツ古」ツ?ョテ」ツつーテ」ツδゥテ」ツδ膝'テ」ツ?ョテゥツ?づァツつケv'テ」ツ?ォテ・ツッツセテ・ツソツ愿」ツ?凖」ツつ凝・ツ?ε」ツ?ョテゥツ?づァツつケv

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() {
    static int num[3];
    cin >> N;
    for (int i = 0; i < 3; i++) {
        cin >> num[i];
    }
    static int min_id[3] = {inf, inf, inf};

    static int group[20000];
    memset(group, -1, sizeof(group));
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < num[i]; j++) {
            int x;
            cin >> x;
            x--;
            group[x] = i;
            min_id[i] = min(min_id[i], x);
        }
    }
    map<int, int> mp;
    int id = 3;

    for (int i = 0; i < 3; i++) {
        old_id[i] = min_id[i];
    }

    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;
        }
    }

    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]);
    }

    // Dijkstra
    for (int s = 0; s < 3; s++) {
        dijkstra(s);
    }

    P ans = {inf, inf};
    for (int v = 0; v < id; v++) {
        ans = min(ans, {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 << ans.first << " " << ans.second + 1 << endl;

    return 0;
}