#include <stdio.h>


struct nod {
	int inf;
	nod *next;
};

const int maxn=100001, maxm=1000001;
int i,n,m,s,D[maxm];
nod *A[maxn];


void citire()
{
	int x,y;
	scanf("%d %d %d",&n,&m,&s);
	for(i=1;i<=m;i++)
	{
		scanf("%d %d",&x,&y);
		nod *q=new nod;
		q->inf=y;
		q->next=A[x];
		A[x]=q;
	}
}
void bfs()
{
	int C[maxn],pi,ps;
	nod *x;
	for(i=1;i<=n;i++) D[i]=-1;
	pi=1; ps=1; C[1]=s; D[s]=0;
	while(ps<=pi)
	{
		
		for(x=A[C[ps]];x!=NULL;x=x->next)
			if(D[x->inf]==-1)
			{
				D[x->inf]=D[C[ps]]+1;
			    pi++;
				C[pi]=x->inf;
			}
		ps++;
	}
}
void afisare()
{
	for(i=1;i<=n;i++)
		if(i==s) printf("0 ");
			else printf("%d ",D[i]);
}
int main()
{
	freopen("bfs.in","r",stdin);
	freopen("bfs.out","w",stdout);
	citire();
	bfs();
	afisare();
}