#include<stdio.h>
#include<malloc.h>
#define Nmax 100005
#define Mmax 1000000

typedef struct nod {
						int inf;
						struct nod *urm;
					} LLin;
LLin *Digraf[Nmax], *ultim[Nmax];
long n, m, s, drum[Nmax], viz[Nmax];
FILE *fin, *fout;


LLin *adauga(LLin *d, int x, long i)
{
	LLin *q;

	if (d==NULL)
	{
		d=(LLin *)malloc(sizeof(LLin));
		d->inf=x;
		d->urm=NULL;
		ultim[i]=d;
	}
	else
	{
		q=(LLin *)malloc(sizeof(LLin));
		q->inf=x;
		q->urm=NULL;
		ultim[i]->urm=q;
		ultim[i]=q;

	}
	return d;
}


void citire()
{
	long x,y,i;

	fin=fopen("bfs.in","r");

	fscanf(fin,"%ld %ld %ld", &n, &m, &s);
	for (i=1; i<=n; i++)
		Digraf[i]=NULL, ultim[i]=NULL, drum[i]=-1, viz[i]=0;

	for (i=1; i<=m; i++)
	{
		fscanf(fin,"%ld %ld", &x, &y);
		Digraf[x]=adauga(Digraf[x],y,x);
	}
}

void bfs(LLin *Digraf[], long s)
{
	long in_coada, sf_coada, coada[Nmax], x;
	LLin *p;

	in_coada=sf_coada=0;
	coada[0]=s;
	drum[s]=0;
	viz[s]=1;

	while (in_coada<=sf_coada)
	{
		x=coada[in_coada++];
		p=Digraf[x];
		while (p!=NULL)
		{
			if (!viz[p->inf])
			{
				coada[++sf_coada]=p->inf;
				drum[p->inf]=drum[x]+1;
				viz[p->inf]=1;
			}
			p=p->urm;
		}
	}

}

void afisare(long drum[Nmax])
{
	long i;
	fout=fopen("bfs.out","w");

	for (i=1; i<=n; i++)
		fprintf(fout, "%ld ", drum[i]);
	fprintf(fout,"\n");

	fclose(fout);
	fclose(fin);
}


int main()
{
	citire();
	bfs(Digraf,s);
	afisare(drum);
	return 0;
}