#include<stdio.h>
#include<stdlib.h>

typedef struct nod{
	int info;
	struct nod *next;
}nod;

typedef nod* lista;

nod *a[1000009];

void adauga_coada(int x,lista*u)
{
	nod *uu = *u;
	nod* nou = (nod*)malloc(sizeof(nod));
	if(uu!=NULL)
		uu->next = nou;
	nou->next = NULL;
	nou->info=x;
	*u = nou;
}

void sterge_coada(lista*p)
{
	nod*q = *p;
	*p = q->next;
	free(q);
}

void adauga(int x,lista*u)
{
	nod *nou = (nod*)malloc(sizeof(nod)),*ultim = *u;
	nou->next = ultim;
	nou->info = x;
	*u = nou;
}

void bfs(int s,int n){
	FILE *g;
	int i,x,y;
	g = fopen("bfs.out","w");
	nod *p = NULL,*u,*q;
	int *d = (int*)malloc((n + 1) * sizeof(int));
	for(i = 1;i <= n;i++)
		d[i] = -1;
	u = p;
	adauga_coada(s,&u);
	p = u;
	d[s] = 0;
	while(p != NULL){
		x = p->info;
		sterge_coada(&p);
		for(q=a[x] ; q!=NULL ; q=q->next)
		{
			y = q->info;
			if(d[y] == -1){
				adauga_coada(y,&u);
				if(p==NULL)
					p = u;
				d[y] = 1  + d[x];
			}
		}
	}
	for(i=1 ; i<=n ; ++i)
		fprintf(g,"%d ",d[i]);
	free(d);
	fclose(g);
}
int main(){
	FILE *f;
	int i,k1,k2;
	f = fopen("grader_test7.in","r");
	int n,m,s;
	fscanf(f,"%d",&n);
	fscanf(f,"%d",&m);
	fscanf(f,"%d",&s);
	for(i=1 ; i<=n ; ++i)
		a[i] = NULL;
	for(i = 0;i < m;i++){
		fscanf(f,"%d%d",&k1,&k2);
		adauga(k2,&a[k1]);
	}
	bfs(s,n);
	return 0;
}