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 <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
inline char nc()
{
	static char buf[100000], *l = buf, *r = buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<class T> void read(T &x)
{
	x = 0; int f = 1, ch = nc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
	while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=nc();}
	x *= f;
}
const int maxn = 10000 + 5;
int N, M;
int c[3];
int bel[maxn];
int val[maxn];
int head[maxn];
int dis[3][maxn];
int mnv[3][maxn];
struct edge
{
    int to, nex;
    edge(int to=0,int nex=0):to(to),nex(nex){}
};
vector<edge> G;
inline void addedge(int u, int v)
{
    G.push_back(edge(v, head[u])), head[u] = G.size() - 1;
    G.push_back(edge(u, head[v])), head[v] = G.size() - 1;
}
void BFS(int s, int id)
{
    static int q[maxn];
    int hd = 0, tl = 0;
    memset(dis[id], -1, sizeof(dis[id]));
    q[tl++] = s;
    dis[id][s] = 0;
    mnv[id][s] = val[s];
    while(hd < tl)
    {
        int u = q[hd++];
        for(int i = head[u]; ~i; i = G[i].nex)
        {
            int v = G[i].to;
            if(dis[id][v] == -1)
            {
                dis[id][v] = dis[id][u] + 1;
                mnv[id][v] = min(mnv[id][u], val[v]);
                q[tl++] = v;
            }
            else if(dis[id][v] == dis[id][u] + 1)
            {
                mnv[id][v] = min(mnv[id][v], mnv[id][u]);
            }
        }
    }
}
void solve()
{
    for(int i = 0; i < 3; ++i) BFS(N + i + 1, i);
    int an0 = -1, an1 = -1;
    for(int i = 1; i <= N + 3; ++i) if(bel[i] == i)
    {
        int t = dis[0][i] + dis[1][i] + dis[2][i];
        int d = min(mnv[0][i], min(mnv[1][i], mnv[2][i]));
        if(an0 == -1 || t < an0)
        {
            an0 = t;
            an1 = d;
        }
        else if(an0 == t)
        {
            an1 = min(an1, d);
        }
    }
    printf("%d %d\n", an0, an1);
}
int main()
{
//    freopen("in", "r", stdin);
    read(N);
    for(int i = 0; i < 3; ++i) read(c[i]);
    for(int i = 1; i <= N + 3; ++i) val[i] = bel[i] = i;
    for(int i = 0; i < 3; ++i)
    {
        int id = N + i + 1;
        for(int j = 1; j <= c[i]; ++j)
        {
            int x; read(x);
            bel[x] = id;
            val[id] = min(val[id], x);
        }
    }
    memset(head, -1, sizeof(head));
    read(M);
    for(int i = 1; i <= M; ++i)
    {
        int u, v; read(u), read(v);
        addedge(bel[u], bel[v]);
    }
    solve();
    return 0;
}