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

typedef struct Node
{ int elem;
  struct Node *next;
}Node;
typedef struct List
 { struct Node *start;
int height;
}List;


inline void queue(List *L,int x)
 {  Node *node;
   node=(Node*)malloc(sizeof(Node));
   node->elem=x;
   node->next=L->start;
   L->start=node;
   L->height++;
 }


inline int dequeue(List *L)
 { 
	Node *index;
	int info;
	if(L->height == 0) return 0;
	 if(L->height > 1)
	 {
		index=L->start;
		while(index->next->next) index=index->next;
		info = index->next->elem;
		free(index->next);
		index->next = NULL;
		L->height--;
	 }
	 else
	 {
		 info = L->start->elem;
		 free(L->start);
		 L->height = 0;
	 }
   
	return info;}

int main()
{
	List L;
	int **a;
	int *viz;
	int i,current,sons,sons_count,d,w;
	int N,M,S;
    FILE * fin;
    FILE * fout;	
	L.start = 0;
	L.height = 0;
    fin=fopen("bfs.in","r");
	fout=fopen("bfs.out","w");
	fscanf(fin,"%d%d%d",&N,&M,&S);
	a=(int**) calloc(M+1,sizeof(int*));
	for(i=1;i<=M;i++)
	{
		a[i] = (int*) calloc(2,sizeof(int));
		fscanf(fin,"%d%d",&a[i][0],&a[i][1]);
	}
	viz = (int *) calloc(N+1,sizeof(int));
	for(i=1;i<=N;i++)
		viz[i] = -1;
	current = S;
	viz[S] = 0;
	sons = 1;
	sons_count = 0;
	d = 1;
	w = 0;
	while(current)
	{
		for(i=1;i<=M;i++)
		{
			if(a[i][0] == current && viz[a[i][1]] == -1)
			{
				sons_count++;
				viz[a[i][1]]=d;
				queue(&L,a[i][1]);
			}
		}

		w++;
		if(w == sons)
		{
			w=0;
			sons=sons_count;
			sons_count=0;
			d++;
		}
		current = dequeue(&L);
	
	}
	for(i=1;i<=N;i++)
		fprintf(fout,"%d ",viz[i]);
	fclose(fin);
	fclose(fout);
  return 0;
}