#include<fstream.h>
#include<stdlib.h>
#define dim 100001



ifstream f("bfs.in");
ofstream g("bfs.out");

unsigned long n,m,x,i,y,z,cont,contor2=0;
unsigned long * a[dim];

unsigned long viz[dim],c[dim];
long rez[dim];



void bf()
{
unsigned long j,prim,ultim,xx;

for(j=1;j<=n;j++)
 {
  viz[j]=0;
  rez[j]=-1;
 }

//cont=0;

viz[x]=1;
rez[x]=0 ;
c[0]=x;
prim=ultim=0;

xx=x;

while(prim<=ultim)
       {
	 xx=c[prim];
	 prim++;

	 for(j=1;j<=a[xx][0];j++)
		{

		 if(!viz[a[xx][j]])

		       {
			 rez[a[xx][j]]=rez[xx]+1;

			 viz[a[xx][j]]=1;

			 ultim++;

			 c[ultim]=a[xx][j];
			}
		     //else return cont;
		}
	}
//  else return cont;

//return -1;
}



int main()
{


f>>n>>m>>x;


for(i=1;i<=n;i++)
{
 a[i]=(unsigned long *)realloc(a[i], sizeof(unsigned long));
 a[i][0]=0;
}


for(i=1;i<=m;i++)
{
 f>>y>>z;

 a[y][0]++;
 a[y]=(unsigned long *)realloc(a[y], (a[y][0]+1)*sizeof(unsigned long));

 a[y][a[y][0]]=z;

}

f.close();


bf();

for(i=1;i<=n;i++) g<<rez[i]<<" ";


g<<'\n';
g.close();
return 0;
}