#include <iostream>
#include <fstream>
#include <vector>
#include <cstdio>
#include <cstring>
#define MAXN 10010

using namespace std;

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

int N, M, S;
int n[MAXN][MAXN], C[MAXN], cost[MAXN], viz[MAXN];

void read()
{
	int x, y;
	
	f >> N >> M >> S;
	for(int i = 0; i < M; ++i)
	{
		f >> x >> y;
		n[x][y] = 1;
		
	}
}

void bfs()
{
	int qi, qf;
	qi = qf = 0;
	memset(cost, -1, MAXN);
	C[0] = S;
	cost[S] = 0;
	viz[S] = 1;
	while(qi <= qf)
	{
		for(int i = 1; i <= N; i++)
			if(n[C[qi]][i] && !viz[i])
				C[++qf] = i, viz[i] = 1, cost[i] = cost[C[qi]]+1;
		
		++qi;
	}
}

void afisare()
{
	for(int i = 1; i <= N; ++i)
	{
		cout << cost[i] << " ";
	}
}

int main()
{
	read();
	bfs();
	afisare();
}