#include <iostream>
#include <vector>
#include <queue>
#include <fstream>

using namespace std;

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

vector <int> mat[100005];
int n, m, s;

void ctr()
{
	fin >> n >> m >> s;

	int x, y;

	for (int i = 0; i < m; ++i)
	{
		fin >> x >> y;
		mat[x].push_back(y);
	}
}

int viz[100005];
int dist[100005];
void fa_viz()
{
	for (int i = 0; i <= n; ++i)
		if (viz[i] == 0 && i != s)viz[i] = -1;
}


void BF(int x)
{
	queue <int> coada;
	int p = 0, u = 0;

	int cd[100005];

	cd[u] = x;
	viz[x] = 1;
	dist[x] = 0;

	while (p <= u)
	{
		x = cd[p];
		p++;

		for (int i = 0; i < mat[x].size(); ++i)
		{
			if (viz[mat[x][i]] == 0)
			{
				cd[++u] = mat[x][i];
				viz[mat[x][i]] = 1;
				dist[mat[x][i]] = dist[x] + 1;
			}
		}
	}
}

void afis_dist()
{
	for (int i = 1; i <= n; ++i)
	{
		if (i == s)fout << 0 << " ";
		else if (dist[i] == 0)fout << -1 <<" ";
		else fout << dist[i] << " ";
	}
	//cout << '\n';
}

void afis_Vecini()
{
	for (int i = 1; i <= n; ++i)
	{
		cout << "Pt nod " << i << ": ";
		for (int j = 0; j < mat[i].size(); ++j)
		{
			cout << mat[i][j] << " ";
		}
		cout << '\n';
	}
}


int main()
{
	ctr();
	//afis_Vecini();
	//cout << "trecc citire\n";
	BF(s);
	//cout << "trec bf\n";
	//fa_viz();
	afis_dist();
	//cout << "trec afis\n";

	return 0;

}