# include <stdio.h>
# include <vector>
//# include <conio.h>
# include <stdlib.h>
# define N 1000020

using namespace std;
typedef struct Node {
	int id;
	vector <int> neighbours;
	int dist;
};
Node graph[N];
int visited[N];
int source, n, m, k = 0;
void readGraph () {
	FILE *f;
	int x, y;
	f = fopen("bfs.in", "r");
	if (!f){ 
		return;
	}
	fscanf(f, "%i %i %i", &n, &m, &source);
	for (int i = 0; i < m; i++) {
		fscanf (f, "%i %i",&x, &y);
		graph[x].id = x;
		graph[x].neighbours.push_back(y);
		graph[x].dist = 0;
	}
	fclose(f);
}

void printGraph () {
	for (int i = 1; i < n; i++){
		printf("%i: ", graph[i].id);
		for (int j = 0; j < graph[i].neighbours.size(); j++){
            printf("%i ", graph[i].neighbours.at(j));    
        }
		printf("\n");
    }
}


void bfs (int start) {
vector <int> queue;
queue.push_back(start);
visited[start] = 1;
	while (queue.size() > 0) {		
		int n = queue.at(0);
		queue.erase(queue.begin());
		for (int i = 0; i < graph[n].neighbours.size(); i++){
			if (visited[graph[n].neighbours.at(i)] ==  0){
				visited[graph[n].neighbours.at(i)] = 1;
				queue.push_back(graph[n].neighbours.at(i));
				graph[graph[n].neighbours.at(i)].dist = graph[n].dist + 1;
			}
		}
	}
}

int main () {
	readGraph();
    //printGraph();
	bfs(source);
	FILE *g = fopen ("bfs.out","w");
	for (int i = 1; i < n + 1; i++){
		if (i != source && graph[i].dist == 0)
			fprintf(g, "-1 ");
		else
			fprintf(g,"%i ", graph[i].dist);
			
	}
	fclose(g);
	//getch();
	return 0;
}