#include<fstream.h>
#include<iostream.h>
int n,m,s,coada[100001],sel[100001],li,ls,t[2][100001],start[100001],p;

int main()
{
int n,m,s,li,ls,i,k,j=0;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
fin>>n>>m>>s;
for(i=1;i<=m;i++){
				 fin>>li>>ls;
				 t[0][i]=ls;
				 t[1][i]=start[li];
				 start[li]=i;
				 }
for(i=1;i<=n;i++)sel[i]=-1;
sel[s]=0;
li=1;
ls=1;
coada[li]=s;
while(li<=ls){
			 k=0;
			 p=start[coada[li]];
			 while(p){
					 if(sel[t[0][p]]==-1)
									  {
									  if(!k){
											k=1;
											j++;
											}
									  ls++;
									  coada[ls]=t[0][p];
									  sel[t[0][p]]=j;
									  }
					 p=t[1][p];
						 }
			 li++;
			 }
for(i=1;i<=n;i++)fout<<sel[i]<<' ';
return 0;
}