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

using namespace std;

typedef struct{
	int dist,culoare;
	vector<int> vecini;
} nod,*pnod;

int n,m,s;
typedef pnod *Graf;
Graf graf;
queue<int> q;
#define inf 0x3f3f3f3f

void read_data(){
	FILE *in = fopen ("bfs.in","r");
	fscanf(in,"%d%d%d",&n,&m,&s);
	s--;
	int node,vecin;
	//graf = (pnod *)malloc(n * (sizeof pnod));
	graf = new pnod[n];
	for (int i = 0; i < n; ++i)
		//graf[i] = (nod *)malloc(sizeof nod);
		graf[i] = new nod;
		
	for (int i = 0; i < m; ++i){
		fscanf(in,"%d%d",&node,&vecin);
		graf[node-1]->vecini.push_back(vecin-1);
	}
	fclose(in);
}

void bfs(){
	for (int i = 0; i < n; ++i){
		graf[i]->dist = inf;
		graf[i]->culoare = 0;
	}
	q.push(s);
	graf[s]->dist = 0;
	int u,v;
	while(!q.empty()){
		u = q.front();
		graf[u]->culoare = 1;
		for (vector<int>::iterator it = graf[u]->vecini.begin(); it != graf[u]->vecini.end(); ++it){
			v = *it;
			if (graf[v]->culoare == 0){
				graf[v]->dist = graf[u]->dist + 1;
				q.push(v);
			}
		}
		q.pop();
	}
}

int main(){
	read_data();
	/*printf("am citit\n");
	for (int i = 0; i < n; ++i){
		printf("Nodul %d are vecinii:\n",i);
		vector<int>::iterator it;
		for (it = graf[i]->vecini.begin(); it != graf[i]->vecini.end(); ++it)
			printf("%d\t", *it);
	}*/
	bfs();
	FILE *out = fopen("bfs.out","w");
	for (int i = 0; i < n; ++i)
			if (graf[i]->dist != inf) fprintf(out,"%d ", graf[i]->dist);
			else fprintf(out,"-1 ");
	fclose(out);
	for (int i = 0; i < n; ++i)
		delete graf[i];
	delete graf;
	return 0;
}