#include<iostream.h>
#include<fstream.h>

ifstream fin("bfs.in");
ofstream fout("bfs.out");

struct nod {
			int x;
			nod *next;
		    }*v[100001],*p;

int i,n,m,s,sel[100001],coada[100001],li=1,ls=1;

void citire()
{
int l1,l2;
fin>>n>>m>>s;
for(i=1;i<=m;i++){
				 fin>>l1>>l2;
				 p=new nod;
				 p->x=l2;
				 p->next=v[l1];
				 v[l1]=p;
				}
}

int main()
{
citire();
for(i=1;i<=n;i++)sel[i]=-1;
sel[s]=0;
coada[li]=s;
while(li<=ls){
			 p=v[coada[li]];
			 while(p){
					 if(sel[p->x]==-1){
									  ls++;
									  coada[ls]=p->x;
									  sel[p->x]=sel[coada[li]]+1;
									  }
					 p=p->next;
					 }
			 li++;
			 }	
for(i=1;i<=n;i++)fout<<sel[i]<<' ';
return 0;
}