#include<stdio.h>
const int N=101000;
int deg[N]={0}, s, a, b, m, n, *vecin[N], drum[N];
void citesc_si_aloc(){
	scanf("%d",&n);
	scanf("%d",&m);
	scanf("%d", &s);
	while(m--){
		scanf("%d", &a);
		scanf("%d", &b);
		deg[a]++;
		}
	fclose(stdin);
	freopen("bfs.in", "r", stdin);
	int i;
	for(i=1; i<=n;++i){
	vecin[i]=new int[1+deg[i]];
	vecin[i][0]=0;
	}
}
void citesc(){
	scanf("%d", &n);
	scanf("%d", &m);
	scanf("%d", &s);
	while(m--){
		scanf("%d", &a);
		scanf("%d", &b);
		vecin[a][++vecin[a][0]]=b;
		}
}


void bfs(int x){
	int p=0, u=0, coada[N];
	int vf, xx;
	for(int i=1; i<=n;++i)
	drum[i]=-1;
	drum[x]=0;
	coada[++u]=x;
	while(p!=u){
		xx=coada[++p];
		for(int i=1; i<=deg[xx];++i){
			 vf=vecin[xx][i];
			 if(drum[vf]==-1)
			 {
				coada[++u]=vf;
				drum[vf]=1+drum[xx];
			 }
		}
	}
}
















int main(){
	freopen("bfs.in", "r", stdin);
	freopen("bfs.out", "w", stdout);
	citesc_si_aloc();
	citesc();
	bfs(s);
	int j;
	for(j=1; j<=n;++j)
		printf("%d ",drum[j]);
	 
















	return 0;
}