/*#include <stdio.h>
#include <vector>

using namespace std;

#define maxn 100010

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

void BFS(int nod)
{
	int i, j;

	memset(Cost, -1, sizeof(Cost));  //	Marchez toate nodurile ca fiind nevizitate

	//	Introduc nodul de start in coada
	L = 1;
	Cost[nod] = 0;
	S[L] = nod;

	for (i = 1; i <= L; i++)	//	Elimin pe rand nodurile din coada
		for (j = 0; j < G[S[i]]; j++)	//	Parcurg vecinii nodului ce urmeaza sa fie eliminat
			if (Cost[A[S[i]][j]] == -1)
			{
				//	Adaug vecinii nevizitati in coada si le calculez distanta
				S[++L] = A[S[i]][j];
				Cost[S[L]] = Cost[S[i]] + 1;
			}
}	

int main()
{
	freopen("bfs.in", "r", stdin);
	freopen("bfs.out", "w", stdout);

	int i, x, y;

	scanf("%d %d %d ", &N, &M, &Start);

	//	Citesc arcele si retin graful sub forma de lista de vecini

	for (i = 1; i <= M; i++) 
	{
		scanf("%d %d ", &x, &y);
		A[x].push_back(y);
	}

	for (i = 1; i <= N; i++) 
		G[i] = A[i].size();

	BFS(Start);

	for (i = 1; i <= N; i++) 
		printf("%d ", Cost[i]);
	printf("\n");

	return 0;
}
*/
#include<stdio.h>
#include<vector>
using namespace std;
#define MAXN 100100
vector <int> nr[MAXN];
int cost[MAXN],grad[MAXN],coada[MAXN];
int n,m,start;
void bfs(){
	int i,j,ul;
	for(i=0;i<=n;++i)
		cost[i]=-1;
	coada[1]=start;
	cost[start]=0;
	ul=1;
	for(i=1;i<=ul;++i){
		for(j=0;j<grad[coada[i]];++j){
			if(cost[nr[coada[i]][j]]==-1){
				coada[++ul]=nr[coada[i]][j];
				cost[coada[ul]]=cost[coada[i]]+1;
			}
		}
	}
}
int main(){
	freopen("bfs.in", "r", stdin);
	freopen("bfs.out", "w", stdout);
	int x,y,i;
	scanf("%d%d%d",&n,&m,&start);
	for(i=0;i<m;++i){
		scanf("%d%d",&x,&y);
		nr[x].push_back(y);
	}
	for(i=1;i<=n;++i)
		grad[i]=nr[i].size();
	bfs();
	for(i=1;i<=n;++i)
		printf("%d ",cost[i]);
	printf("\n");
	fclose(stdin);
	fclose(stdout);
	return 0;
}