#include<stdio.h>
#include<string.h>
FILE *f=freopen("bfs.out","wt",stdout);
int n,s;
int cost[100001];
void BFS();
struct nod
{
	int info;
	nod *urm;
};
typedef nod *Lista;
void Insert(Lista &prim,Lista p,int x)
{
	Lista q=new nod; 
    q->info=x;
	if(prim) { q->urm=p->urm; p->urm=q;}
	else { q->urm=prim; prim=q;}
}
Lista L[100001],Ultim[100001];
int main()
{int  i,m,x,y;
	freopen("bfs.in","rt",stdin);
	scanf("%d %d %d",&n,&m,&s);
	for(i=1;i<=m;++i) 
	  {scanf("%d %d",&x,&y);
	  if(L[x]) Insert(L[x],Ultim[x],y),Ultim[x]=Ultim[x]->urm;
	  else  Insert(L[x],NULL,y),Ultim[x]=L[x];
	  }
	BFS();
	for(i=1;i<=n;++i) printf("%d ",cost[i]);
	return 0;
}
bool uz[100001];
void BFS()
{   Lista p; 
 	int  prim,ultim,x,y;
	int  v[100001];
	v[1]=s; prim=ultim=1; uz[s]=1;  
	    memset(cost,-1,sizeof(cost));  cost[s]=0;
	    while(ultim>=prim)
		{
			x=v[prim++];
			for(p=L[x];p;p=p->urm)
				if(!uz[p->info])
				  {y=p->info;
					  uz[y]++;
					  cost[y]=cost[x]+1;
					  v[++ultim]=y;
				}
		}
}