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

template <class Cost = int>
struct Edge {
    int src, dst;
    Cost cost;
    Edge(int src = -1, int dst = -1, Cost cost = 1)
        : src(src), dst(dst), cost(cost){};

    bool operator<(const Edge<Cost>& e) const { return this->cost < e.cost; }
    bool operator>(const Edge<Cost>& e) const { return this->cost > e.cost; }
};

template <class Cost = int>
using Graph = std::vector<std::vector<Edge<Cost>>>;

std::vector<int> bfs(const Graph<>& graph, int s) {
    std::vector<int> dist(graph.size(), -1);
    std::queue<int> que;

    dist[s] = 0;
    que.push(s);

    while (!que.empty()) {
        int v = que.front();
        que.pop();

        for (auto e : graph[v]) {
            int u = e.dst;
            if (dist[u] != -1) continue;
            dist[u] = dist[v] + 1;
            que.push(u);
        }
    }

    return dist;
}

void solve() {
    int n;
    std::cin >> n;

    std::vector<std::set<int>> gs(3);
    {
        std::vector<int> ms(3);
        for (auto& m : ms) std::cin >> m;
        for (int i = 0; i < 3; ++i) {
            while (ms[i]--) {
                int v;
                std::cin >> v;
                gs[i].insert(--v);
            }
        }
    }

    auto trans = [&](int v) {
        for (int i = 0; i < 3; ++i) {
            if (gs[i].count(v)) return n + i;
        }
        return v;
    };

    Graph<> graph(n + 3);
    int m;
    std::cin >> m;
    while (m--) {
        int u, v;
        std::cin >> u >> v;
        --u, --v;

        u = trans(u), v = trans(v);
        graph[u].emplace_back(u, v);
        graph[v].emplace_back(v, u);
    }

    std::vector<std::vector<int>> dss(3);
    for (int i = 0; i < 3; ++i) {
        dss[i] = bfs(graph, n + i);
    }

    int ans = n;
    std::vector<int> rs;

    for (int v = 0; v < n; ++v) {
        int u = trans(v);
        int dsum = dss[0][u] + dss[1][u] + dss[2][u];

        if (dsum < ans) {
            rs.clear();
            ans = dsum;
        }
        if (dsum == ans) rs.push_back(u);
    }

    std::vector<std::set<int>> ids(3);
    std::function<void(int, int)>
        dfs = [&](int v, int i) {
            if (ids[i].count(v)) return;

            ids[i].insert(v);
            for (auto e : graph[v]) {
                int u = e.dst;
                if (dss[i][u] >= dss[i][v]) continue;
                dfs(u, i);
            }
        };

    for (auto r : rs) {
        for (int i = 0; i < 3; ++i) {
            dfs(r, i);
        }
    }

    std::set<int> col;
    for (int i = 0; i < 3; ++i) {
        col.insert(gs[i].begin(), gs[i].end());
        col.insert(ids[i].begin(), ids[i].end());
    }

    std::cout << ans << " " << *col.begin() + 1 << std::endl;
}

int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);

    solve();

    return 0;
}