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

using namespace std;

int M,N;

vector<int> L[100000];
bool visited[100000]; // vector pentru marcarea nodurilor
int C[100000];

void breadth(int nod){
	queue<int> Q;
	C[nod]=1;
	Q.push(nod);
	visited[nod]=true;		
	vector<int>::iterator it; 
	while(!Q.empty()){
		int i=Q.front();
		Q.pop();
		for (it = L[i].begin(); it != L[i].end(); ++it) {
			if(visited[*it]==false){
				C[*it]=C[i]+1;
				visited[*it]=true;
				Q.push(*it);
			}
		}
	}
}

int main(){
	FILE* f= fopen("bfs.in","rt");
	FILE* g= fopen("bfs.out","wt");
	
	int nod;
	fscanf(f,"%d %d %d",&N,&M,&nod);
	nod--;

	int x,y;

	for(int i=0;i<M;i++){
		fscanf(f,"%d %d",&x,&y);
		L[x-1].push_back(y-1);	
	}

	breadth(nod);

	for(int i=0;i<N;i++)
		fprintf(g,"%d ",C[i]-1);

	fclose(g);
	fclose(f);
	return 0;
}