#include <iostream>
#include <vector>
#include <fstream>
#define MAXN 100010
using namespace std;

vector<int> A[MAXN];
int Cost[MAXN],C[MAXN];

int N,M,S;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

int BFS(int x) {
	int prim,ultim,i;
	
	memset(Cost,-1,sizeof(Cost));
	
	Cost[x] = 0;	
	prim = ultim = 0;
	C[0] = x;
	
	while (prim <= ultim) {
		x = C[prim++];
		for (i=1;i<=A[x][0];++i) {
			if (Cost[A[x][i]] == -1) {
				Cost[A[x][i]] = Cost[x] + 1;
				C[++ultim] = A[x][i];
			}
		}
	}
	
}

int main() {
	int x,y,i;
	fin >> N >> M >> S;
	
	for (i=1;i<=N;++i) {
		A[i].push_back(0);
	}
	
	for (i=1;i<=M;++i) {
		fin >> x >> y;
		A[x].push_back(y);
	}
	
	for (i=1;i<=N;++i) {
		A[i][0] = A[i].size() - 1;
	}
	
	BFS(S);
	
	for (i=1;i<=N;++i)
		fout << Cost[i] << " ";
		
	fout << endl;	

	fin.close();
	fout.close();
	
	return 0;
}