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;
int n,a,b,c,A[11111],B[11111],C[11111],dp[11111][11],m,x[555555],y[555555],id[11111],all,dist[11111],mn,mnp,toi[11111];
vector<int> g[11111];
void dijk(int msk)
{
	for (int i=1;i<=all;i++) dist[i]=dp[i][msk];
	priority_queue<pair<int,int> > pq;
	for (int i=1;i<=all;i++) pq.push(make_pair(-dist[i],i));
//	cout<<msk<<":"<<endl;
//	for (int i=1;i<=all;i++) cout<<dist[i]<<" ";
//	cout<<endl;
	while(!pq.empty())
	{
		int x=pq.top().second,y=-pq.top().first;
		pq.pop();
		if (dist[x]!=y) continue;
		for (int j=0;j<g[x].size();j++)
		{
			int to=g[x][j];
			if (dist[to]>dist[x]+1)
			{
				dist[to]=dist[x]+1;
				pq.push(make_pair(-dist[to],to));
			}
		}
	}
}
int main()
{
	scanf("%d%d%d%d",&n,&a,&b,&c);
	for (int i=1;i<=n;i++) id[i]=i+3;
	for (int i=1;i<=a;i++)
	{
		scanf("%d",&A[i]);
		id[A[i]]=1;
	}
	for (int i=1;i<=b;i++)
	{
		scanf("%d",&B[i]);
		id[B[i]]=2;
	}
	for (int i=1;i<=c;i++)
	{
		scanf("%d",&C[i]);
		id[C[i]]=3;
	}
	scanf("%d",&m);
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d",&x[i],&y[i]);
		g[id[x[i]]].push_back(id[y[i]]);
		g[id[y[i]]].push_back(id[x[i]]);
	}
	all=n+3;
	for (int i=1;i<=all;i++)
	{
		for (int j=0;j<8;j++) dp[i][j]=1e9;
		dp[i][0]=1;
	}
	dp[1][1]=dp[2][2]=dp[3][4]=1;
	for (int i=1;i<8;i++)
	{
		for (int k=1;k<=all;k++)
		{
			for (int h=0;h<8;h++)
			{
				if ((i&h)!=h) continue;
				for (int p=0;p<g[k].size();p++)
				{
					dp[k][i]=min(dp[k][i],dp[g[k][p]][h]+dp[k][i^h]);
				}
			}
		}
		dijk(i);
		for (int k=1;k<=all;k++) dp[k][i]=dist[k];
	}
	mn=1e9;
	for (int i=1;i<=3;i++)
	{
		for (int j=1;j<=n;j++)
		{
			if (id[j]==i) 
			{
				toi[i]=j;
				break;
			}
		}
	}
	for (int i=4;i<=all;i++) toi[i]=i-3;
	for (int i=1;i<=all;i++)
	{
		if (dp[i][7]<mn || (toi[i]<mnp && dp[i][7]==mn))
		{
			mn=dp[i][7];
			mnp=toi[i];
		}
	}
	printf("%d %d\n",mn-1,mnp);
	return 0;
}