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

#define max 100010

int vf, muc, start;
int* adia[max];
int dim[max];

void citire();
void bfs();
void afisareListe();
void afisareDist();

int main(){

	
	citire();
	for(int i = 1; i <= vf; i++)
		dim[i] = -1;
	bfs();
	//afisareListe();
	afisareDist();
	return 0;
}

void citire(){
	FILE* f = fopen("bfs.in", "r");
	fscanf(f,"%d%d%d", &vf, &muc, &start);

	for(int i = 1; i <= vf; i++)
    {
        adia[i] = (int *)realloc(adia[i], sizeof(int));
        adia[i][0] = 0;
    }

    int x, y;
    for(int i = 0; i < muc; i++)
    {
        fscanf(f,"%d%d", &x, &y);
        adia[x][0]++;
        adia[x] = (int *)realloc(adia[x], (adia[x][0] + 1) * sizeof(int));
        adia[x][adia[x][0]] = y;
    }
	fclose(f);
	
}

void bfs(){
	int coada[max], mar = 1, cur = start;
	dim[cur] = 0;
	coada[mar] = cur;

	for(int i = 1; i <= mar; i++){
		cur = coada[i];
		for(int j = 1; j <= adia[cur][0]; j++){
			if(dim[adia[cur][j]] == -1){
				//printf("%d\n", adia[cur][j]);
				coada[++mar] = adia[cur][j];
				dim[adia[cur][j]] = dim[cur] + 1;
			}
		}
	}

}

void afisareListe(){
	FILE* g = fopen("fis.out", "w");
	
	for(int i = 1; i <= vf; i++){
		fprintf(g, "%d: ", i);
		for(int j = 1; j <= adia[i][0]; j++)
			fprintf(g, "%d ", adia[i][j]);
		fprintf(g, "\n");
	}
	
	fclose(g);
	
}

void afisareDist(){
	FILE* g = fopen("bfs.out", "w");
	for(int i = 1; i <= vf ;i++)
		fprintf(g, "%d ", dim[i]);
	//fprintf(g, "caia e tare\n"	);
	fclose(g);
}