#include<fstream.h>
ifstream fin("bfs.in");
ofstream fout("bfs.out");
#define max 1000000
struct nod{int info;nod *urm;}*g[max];
long n,m,s,c[max];
int dr[max];


void adauga(int a,int b)
 {nod *f=new nod;
  f->info=b;
  f->urm=g[a];
  g[a]=f;
  }


void bf()
{long p,u,i;
for(i=1;i<=n;i++)dr[i]=-1;
p=u=1;
c[1]=s;
dr[s]=0;
nod *d;
while(p<=u)
  { for(d=g[c[p]];d!=NULL;d=d->urm)
      if(dr[d->info]==-1)
	  {u++;
	   c[u]=d->info;
	   dr[d->info]=dr[c[p]]+1;
	   }
       p++;
  }

}

int main()
{fin>>n>>m>>s;

 long i,j,x;

 for(i=1;i<=m;i++)
   {fin>>x>>j;
    adauga(x,j);
    }
bf();
for(i=1;i<=n;i++)
   fout<<dr[i]<<" ";
fin.close();
fout.close();
return 0;

}