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>
#define INF 1000000
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int a[3],n,m;
int type[10009];
vector<int> G[10005];
int dist[4][10005];

int bfs(int s){
	for(int i=3;i<4;i++){
		queue<int> que;
		for(int j=0;j<n+3;j++){
			dist[i][j]=INF;
		}
		dist[i][s]=0;
		que.push(s);
		while(que.size()){
			int v=que.front();
			que.pop();
			for(int k=0;k<G[v].size();k++){
				int nv=G[v][k];
				if(dist[i][nv]==INF){
					dist[i][nv]=dist[i][v]+1;
					que.push(nv);
				}
			}
		}
	}
	int bes=s;
	for(int i=0;i<n;i++){
		for(int j=0;j<3;j++){
			if((dist[3][i]+dist[j][i])==dist[j][s]){
				bes=min(bes,i);
			}
		}
	}
	return bes;
}

int main(void){
	scanf("%d%d%d%d",&n,&a[0],&a[1],&a[2]);
	memset(type,-1,sizeof(type));
	for(int i=0;i<3;i++){
		for(int j=0;j<a[i];j++){
			int b;
			scanf("%d",&b);
			b--;
			type[b]=i;
		}
	}
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		u--;
		v--;
		if(type[u]>=0){
			u=n+type[u];
		}
		if(type[v]>=0){
			v=n+type[v];
		}
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for(int i=0;i<3;i++){
		type[n+i]=i;
	}
	for(int i=0;i<3;i++){
		queue<int> que;
		for(int j=0;j<n+3;j++){
			dist[i][j]=INF;
			if(type[j]==i){
				dist[i][j]=0;
				que.push(j);
			}
		}
		while(que.size()){
			int v=que.front();
			que.pop();
			for(int k=0;k<G[v].size();k++){
				int nv=G[v][k];
				if(dist[i][nv]==INF){
					dist[i][nv]=dist[i][v]+1;
					que.push(nv);
				}
			}
		}
	}
	int ans=INF;
	for(int i=0;i<n+3;i++){
		int aa=dist[0][i]+dist[1][i]+dist[2][i];
		ans=min(aa,ans);
	}
	int bes=114514;
	for(int i=0;i<n+3;i++){
		if(type[i]>=0){
			bes=min(bes,i);
		}
		int aa=dist[0][i]+dist[1][i]+dist[2][i];
		if(aa==ans){
			bes=min(bfs(i),bes);
		}
	}
	printf("%d %d\n",ans,bes+1);
	return 0;
}