#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, *unV;
	
	unV=(int*)calloc(2*m, sizeof(int));
	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));
	
	int cm=m;
	int *p=unV;
	while(m--)
	{
		int x,y;
		fscanf(f, "%i %i", &x, &y);
		*p=x; p++; *p=y; p++;
		LV[x]++;
	}
	
	for(p=unV;p!=unV+2*cm;)
	{
		int x,y,*q=v,var=0;
		x=*p; p++; y=*p; p++;
		for(var=0;var<x;var++)
			q+=LV[var];
		while(*q!=0)
			q++;
		*q=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;
}