#include<cstdio>
using namespace std;

FILE *f;
FILE *g;

typedef struct nod
{
	int inf;
	nod *urm;
} NOD;

typedef NOD *graf[100010];
graf G;

int n,m,s;
int c[100010],niv[100010],viz[100010];
void citire()
{
	f=fopen("bfs.in","r");
	fscanf(f,"%d %d %d",&n,&m,&s);
	NOD *p;
	int a,b;
	for(int i=1;i<=m;i++)
	{
		fscanf(f,"%d %d",&a,&b);
		p=new NOD;
		p->inf=b; p->urm=G[a]; G[a]=p;
	}
}

void bfs()
{
	int pr,ul=pr=1;
	c[pr]=s;
	viz[s]=1;
	while(pr<=ul)
	{
		NOD *p;
		p=G[c[pr]];
		while(p)
		{
			if(!viz[p->inf])
			{
				c[++ul]=p->inf;viz[p->inf]=1;
				niv[p->inf]=niv[c[pr]]+1;
			}
			p=p->urm;
		}
		pr++;
	}
}

void afis()
{
	g=fopen("bfs.out","w");
	for(int i=1;i<=n;i++)
		if(i==s)
			fprintf(g,"0 ");
		else
			if(!niv[i])
				fprintf(g,"-1 ");
			else
				fprintf(g,"%d ",niv[i]);
	fprintf(g,"\n");
	fclose(f);
	fclose(g);
}

int main()
{
	citire();
	bfs();
	afis();
	return 0;
}