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;

void djk(const vector<vector<int>>&edges, vector<int>&memo,vector<int>&minid,int start) {
	queue<pair<int, int>>que;
	que.push(make_pair(start, 0));
	memo[start] = 0;
	minid[start] = start;
	while (!que.empty()) {
		auto atop(que.front());
		que.pop();
		for (auto e : edges[atop.first]) {
			const int nexttime = atop.second + 1;
			if (memo[e] > nexttime) {
				memo[e] = nexttime;
				que.push(make_pair(e, nexttime));
				minid[e] = min(e, minid[atop.first]);
			}
			else if (memo[e] == nexttime) {
				minid[e] = min(minid[e], minid[atop.first]);
			}
		}
	}
	return;
}

int main() {
	int nums[3];
	int N; cin >> N >> nums[0] >> nums[1] >> nums[2];
	map<int, int>mp;
	for (int j = 0; j < 3; ++j) {
		for (int i = 0; i < nums[j]; ++i) {	
			int n; cin >> n;
			n--; mp[n] = N + j;
		}
	}
	int M; cin >> M;
	vector<vector<int>>edges(N + 3);
	for (int i = 0; i < M; ++i) {
		int x, y; cin >> x >> y; x--; y--;
		int gx, gy;
		if (mp.find(x) == mp.end())gx = x;
		else gx = mp[x];
		if (mp.find(y) == mp.end())gy = y;
		else gy = mp[y];
		if (gx == gy)continue;
		edges[gx].push_back(gy);
		edges[gy].push_back(gx);
	}
	vector<vector<int>>memos(3,vector<int>(N+3,1e9));
	vector<vector<int>>froms(3,vector<int>(N+3,1e9));
	for (int i = 0; i < 3; ++i) {
		djk(edges, memos[i], froms[i], N + i);
	}
	pair<int, vector<int>>minids(make_pair(int(1e8),vector<int>(0)));
	for (int i = 0; i < N + 3; ++i) {
		if (mp.find(i) != mp.end())continue;
		else {
			int sum = 0;
			for (int j = 0; j < 3; ++j) {
				sum += memos[j][i];
			}
			if (sum < minids.first) {
				minids.first = sum;
				minids.second = vector<int>(1, i);
			}
			else if (sum == minids.first) {
				minids.second.emplace_back(i);
			}
		}
	}
	int ans = 1e8;
	for (auto id : minids.second) {
		for (int i = 0; i < 3; ++i) {
			ans = min(ans, froms[i][id]);
		}
	}
	for (int i = 0; i < N; ++i) {
		if (mp.find(i) != mp.end())ans = min(ans, i);
	}
	ans++;
	cout << minids.first <<" "<< ans << endl;
	return 0;
}