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;

const int INF = 1 << 25;
typedef pair<int, int> P;
typedef pair<P, int> PP;
int N, M;
int minId[3] = { INF, INF, INF };
int S[3];
P dist[3][20000];
int group[20000];
vector<int> G[20000];

void bfs(int s){
	priority_queue<PP, vector<PP>, greater<PP>> q;
	for(int i = 0; i < N + 3; i++){
		dist[s][i] = { INF, INF };
	}
	dist[s][S[s]] = { 0, minId[s] };
	q.push({ { 0, minId[s] }, S[s] });

	while(q.size()){
		PP p = q.top();
		q.pop();
		int v = p.second;
		if(dist[s][v] != p.first) continue;
		int d = p.first.first, id = p.first.second;
		for(auto u : G[v]){
			P nd = { d + 1, min(u, id) };
			if(u >= N || v >= N){
				nd.first--;
			}
			if(dist[s][u] > nd){
				dist[s][u] = nd;
				q.push({ nd, u });
			}
		}
	}
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	memset(group, -1, sizeof group);
	int A[3];
	cin >> N >> A[0] >> A[1] >> A[2];
	S[0] = N, S[1] = N + 1, S[2] = N + 2;
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < A[i]; j++){
			int a;
			cin >> a;
			a--;
			group[a] = i;
			minId[i] = min(minId[i], a);
			G[S[i]].push_back(a);
			G[a].push_back(S[i]);
		}
	}
	cin >> M;
	for(int i = 0; i < M; i++){
		int x, y;
		cin >> x >> y;
		x--, y--;
		G[x].push_back(y);
		G[y].push_back(x);
	}

	for(int i = 0; i < 3; i++){
		bfs(i);
	}

	P ans = { INF, INF };
	for(int i = 0; i < N; i++){
		int sum = 0, id = INF;
		for(int j = 0; j < 3; j++){
			sum += dist[j][i].first;
			id = min(id, dist[j][i].second);
		}
		ans = min(ans, { sum, id });
	}
	cout << ans.first << " " << ans.second + 1 << endl;
}