#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,j, l;
	
	fscanf(f, "%i %i %i", &n, &m, &s);
	int *q, *viz, *dist, *v;
	v=(int*)calloc((n+1)*(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);
		v[x*n]++;
		v[x*n + v[x*n]]=y;
		//v[y][++v[y][0]]=x;
	}
	
	
	q[0]=i=s; l=1;
	while(l)
	{
		for(j=1;j<=v[i*n];j++)
			if(viz[v[i*n+j]]==0 && NuEInCoada(q, l, v[i*n+j]))
				Enqueue(q, &l, v[i*n+j], 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;
}