#include<cstdio>
using namespace std;
struct nod{ int c;
			nod*lg;
		  }*vf[100000],*r;
int p,q,n,m,i,s,x,y,que[1000000],ave[100000];
int main()
{ freopen("bfs.in","r",stdin);
  freopen("bfs.out","w",stdout);
  scanf("%d%d%d",&n,&m,&s);
  for(i=1;i<=n;i++) { vf[i]=new nod;
	                  vf[i]->c=0;
					  vf[i]->lg=0;
					}  
  for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); 
 					  r=new nod;r->c=y;
					  r->lg=vf[x]->lg;
					  vf[x]->c++;
					  vf[x]->lg=r;
					}
  p=q=1;
  ave[s]=1;que[1]=s;
  while(p<=q) { r=vf[que[p]]->lg;
			    while(r) { if(!ave[r->c]) { que[++q]=r->c;
											ave[r->c]=1+ave[que[p]];
										  }
						   r=r->lg;
						 }
			    p++;
              }		
  for(i=1;i<=n;i++)printf("%d ",ave[i]-1); 
  /*for(i=1;i<=n;i++) { printf("%d::%d ,",i,vf[i]->c);
					  r=vf[i]->lg;
					  while(r) printf("%d ",r->c),r=r->lg;
					  printf("\n");
				    }*/					  
  fclose(stdin);
  fclose(stdout);
  return 0;
}