# include <stdio.h>

int n,m,s,d[100000];

struct lista{
	int inf;
	lista *adr;
};
lista *v[10000];

void adauga(lista *&vf,int x){
	lista *aux=new lista;
	aux->inf=x;
	aux->adr=vf;
	vf=aux;
}

void citire(){
	int i,j,k;
	scanf("%d%d%d",&n,&m,&s);
	for(k=1;k<=m;k++){
		scanf("%d%d",&i,&j);
		adauga(v[i],j);
	}
}

void adauga_c(lista *&u,int x){
	lista *aux=new lista;
	aux->inf=x;
	aux->adr=NULL;
	u->adr=aux;
	u=aux;
}

void init(){
	int i;
	for(i=1;i<=10000;i++)
		d[i]=-1;
}

void bfs(int s){   
    int x,y;   
    lista *p=new lista;
	lista *u,*aux;   
    p->inf=s;   
    p->adr=NULL;   
    u=p;   
    d[s]=0;   
    while(p){   
        x=p->inf;   
        for(aux=v[x];aux!=NULL;aux=aux->adr){   
            y=aux->inf;   
            if(d[y]==-1){   
                adauga_c(u,y);   
                d[y]=1+d[x];   
            }   
        }   
        aux=p;   
        p=p->adr;   
        delete aux;   
    }   
}   

void scrie(){   
    for(int i=1;i<=n;i++)   
        printf("%d ",d[i]);   
}   

int main(){   
    freopen("bfs.in","r",stdin);   
    freopen("bfs.out","w",stdout);   
    citire();   
    init();   
    bfs(s);   
    scrie();   
    return 0;   
}