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 <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll;
#define rep(i, a, b) for (int i = a; i <= b; ++ i)
const int maxn = 10005, maxm = 2000005, inf = 1000000007; 
using namespace std;
bool vis[maxn];
int n, N[5], bel[maxn], m, e, ter[maxm], nxt[maxm], lnk[maxn], w[maxm], dis[maxn][8], opt[maxn];
void add(int x, int y, int z) { ter[++ e] = y, nxt[e] = lnk[x], lnk[x] = e, w[e] = z; }
void spfa(int st) {
	int he = 0, ta = 0;
	rep(i, 1, n) vis[i] = true;
	rep(i, 1, n) if (dis[i][st] != inf) opt[++ ta] = i, vis[i] = false;
	for ( ; he != ta; ) {
		he = (he + 1) % maxn; int u = opt[he];
		for (int i = lnk[u]; i; i = nxt[i]) {
			if (dis[u][st] + w[i] < dis[ter[i]][st]) {
			dis[ter[i]][st] = dis[u][st] + w[i];
			if (vis[ter[i]]) vis[ter[i]] = false, ta = (ta + 1) % maxn, opt[ta] = ter[i];
		}
	}
		vis[u] = true;
	}
}
int main() {
	scanf("%d%d%d%d", &n, &N[1], &N[2], &N[3]); int x, las, y;
	rep(col, 1, 3) {
		las = 0;
		rep(i, 1, N[col]) {
			scanf("%d", &x), bel[x] = col;
			if (las) add(las, x, 0), add(x, las, 0);
			las = x;
		}
	}
	scanf("%d", &m);
	rep(i, 1, m) scanf("%d%d", &x, &y), add(x, y, 1), add(y, x, 1);
	rep(i, 1, n) rep(j, 0, 7) dis[i][j] = inf;
	rep(col, 1, 3) {
		int st = (1 << (col - 1));
		rep(i, 1, n) if (bel[i] == col) dis[i][st] = 0;
		spfa(st);
	}
	int st = 3;
	rep(i, 1, n) dis[i][st] = min(dis[i][1] + dis[i][2], inf);
	spfa(st);
	st = 5;
	rep(i, 1, n) dis[i][st] = min(dis[i][1] + dis[i][4], inf);
	spfa(st);
	st = 6;
	rep(i, 1, n) dis[i][st] = min(dis[i][2] + dis[i][4], inf);
	spfa(st);
	st = 7;
	rep(i, 1, n) 
		dis[i][st] = min(dis[i][st], min(dis[i][1] + dis[i][2], inf) + dis[i][4]),
		dis[i][st] = min(dis[i][st], dis[i][1] + dis[i][6]),
		dis[i][st] = min(dis[i][st], dis[i][2] + dis[i][5]),
		dis[i][st] = min(dis[i][st], dis[i][4] + dis[i][3]);
	spfa(st);
	int ans = inf, id = 0;
	rep(i, 1, n) 
		if (dis[i][7] < ans) {
			ans = dis[i][7], id = i;
		}
	printf("%d %d\n", ans, id); 
	return 0;
}