#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

ifstream f("bfs.in");
ofstream g("bfs.out");

vector <int> A[100000];
int G[100000], S[100000], Cost[100000];
int M,N,L;

void BFS(int nod)
{
	int i, j;
	for(i = 0 ; i < 100000; i++) {
		Cost[i] = -1;
	}
	L = 1;
	Cost[nod] = 0;
	S[L] = nod;
	for (i = 1; i <= L; i++) {
		for (j = 0; j < G[S[i]]; j++) {	
			if (Cost[A[S[i]][j]] == -1) {
				S[++L] = A[S[i]][j];
				Cost[S[L]] = Cost[S[i]] + 1;
			}
		}
	}
}	


int main()
{
	int i,N,M,S,x,y;
	f>>N>>M>>S;
	for (i = 1; i <= M; i++)  {
		f>>x>>y;
		A[x].push_back(y);
	}
	for (i = 1; i <= N; i++) {
		G[i] = A[i].size();
	}
	BFS(S);
	for (i = 1; i <= N; i++)  {
		g<<Cost[i]<<" ";
	}
}