#include<stdio.h>
#include<fstream.h>
ifstream f("bfs.in");
ofstream g("bfs.out");
typedef struct nod{
	int nr;
	nod *ante;
};
nod *p,*l[1000001];
int v[1000001],c[1000001],ic,sc,k=0,a[1000001];
long n,m,s,i,j;
int bf(){
	nod *q;
	k++;
	while(ic<=sc){
	   q=l[c[ic]];
	   while(q){
		   if(!v[q->nr]){
			   sc++;
			   c[sc]=q->nr;
			   v[q->nr]=1;
			   if(a[q->nr]==0)
			    a[q->nr]=k;
	      }
		  
		   q=q->ante;
	   }
	   ic++;
	   bf();
	}
	return 0;
}
int main(){
	f>>n>>m>>s;
	while(f>>i>>j){
		p=new nod;
		if(i!=j){
		  p->nr=j;
		  p->ante=l[i];
		  l[i]=p;
		}
	}
	ic=1;sc=1;
	c[1]=s;
	v[s]=1;
	a[s]=0;
	bf();
	for(i=1;i<=n;i++){
		if((a[i]==0)&&(i!=s)) g<<("-1 ");
		else  g<<a[i]<<' ';
	}
	g<<"\n";
	f.close();
	g.close();
		return 0;
}