#include <stdio.h>
#include <stdlib.h>

void Enqueue(int q[], int *l, int x, int dist[], int tata)
{
	q[*l]=x;
	dist[x]=dist[tata]+1;
	*l=*l+1;
}

void Afara(FILE* g, int q[], int *l, int sol[])
{
	sol[q[0]]=1;
	int i;
	*l=*l-1;
	for(i=0;i<*l;i++)
		q[i]=q[i+1];
}

int NuEInCoada(int q[], int l, int x)
{
	int i;
	for(i=0;i<l;i++)
		if(q[i]==x)
			return 0;
	return 1;
}

int main ()
{
	FILE *f=fopen("bfs.in", "rt"), *g=fopen("bfs.out", "wt");
	int n, m, s;
	int i, l;
	
	fscanf(f, "%i %i %i", &n, &m, &s);
	int *q, *viz, *dist, *v, *LV;
	v=(int*)calloc(m+1, sizeof(int));
	LV=(int*)calloc(n+1, sizeof(int));
	q=(int*)calloc(n+1, sizeof(int));
	viz=(int*)calloc(n+1, sizeof(int));
	dist=(int*)calloc(n+1, sizeof(int));
	
	while(m--)
	{
		int x,y;
		fscanf(f, "%i %i", &x, &y);
		LV[x]++;
	}
	
	fclose(f);
	f=fopen("bfs.in", "rt");
	fscanf(f, "%i %i %i", &n, &m, &s);
	
	while(m--)
	{
		int x,y,*p=v,var=0;
		fscanf(f, "%i %i", &x, &y);
		for(var=0;var<x;var++)
			p+=LV[var];
		while(*p!=0)
			p++;
		*p=y;
		//v[y][++v[y][0]]=x;
	}
	
	
	q[0]=i=s; l=1;
	while(l)
	{
		int *p=v,var,*sf;
		for(var=0;var<i;var++)
			p+=LV[var];
		sf=p+LV[i];
		for(;p!=sf;p++)
		{
			if(viz[*p]==0 && NuEInCoada(q, l, *p))
				Enqueue(q, &l, *p, dist, i);
		}
		Afara(g, q, &l, viz);
		i=q[0];
	}
	
	for(i=1;i<=n;i++)
		fprintf(g,"%i ", (dist[i]==0 && i!=s) ? -1 : dist[i]);
	return 0;
}