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<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

const int N=10005;
const int M=500005;

struct edge{
  int u,v,next;
}G[M<<1];
int head[N],inum;
inline void add(int u,int v,int p){
  G[p].u=u; G[p].v=v; G[p].next=head[u]; head[u]=p;
}

int Q[5000005],l,r;
int ins[N];

int *F,idx[N];
inline bool cmp(int x,int y){
  return F[x]<F[y];
}

int n,m;
#define V G[p].v
inline void SPFA(int *f){
  l=r=-1;
  F=f; for (int i=1;i<=n;i++) idx[i]=i;
  sort(idx+1,idx+n+1,cmp); 
  for (int i=1;i<=n;i++) Q[++r]=idx[i],ins[idx[i]]=1;
  while (l<r){
    int u=Q[++l]; ins[u]=0;
    for (int p=head[u];p;p=G[p].next)
      if (f[V]>f[u]+1){
	f[V]=f[u]+1;
	if (!ins[V])
	  Q[++r]=V,ins[V]=1;
      }
  }
}
int fat[N];
int a[5][N];

int f[1<<3][N];

int main(){
  int iu,iv;
  read(n); for (int i=0;i<3;i++) read(*a[i]);
  for (int i=1;i<=n;i++) fat[i]=i;
  for (int i=0;i<3;i++){
    for (int j=1;j<=*a[i];j++)
      read(a[i][j]);
    sort(a[i]+1,a[i]+*a[i]+1);
    for (int j=2;j<=*a[i];j++)
      fat[a[i][j]]=a[i][1];
  }
  read(m);
  for (int i=1;i<=m;i++)
    read(iu),read(iv),add(fat[iu],fat[iv],++inum),add(fat[iv],fat[iu],++inum);
  memset(f,0x3f,sizeof(f));
  for (int i=0;i<3;i++)
    f[1<<i][a[i][1]]=0;
  for (int i=1;i<(1<<3);i++){
    for (int j=1;j<=n;j++)
      for (int k=(i-1)&i;k;k=(--k)&i)
	f[i][j]=min(f[i][j],f[k][j]+f[i^k][j]);
    SPFA(f[i]);
  }
  int ans=1<<30,idx;
  for (int i=1;i<=n;i++)
    if (f[7][i]<ans)
      ans=f[7][i],idx=i;
  printf("%d %d\n",ans,idx);
  return 0;
}