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

using namespace std;

class GrafOr
{
private:

	int n, m;

	vector <vector <int>> vfAdiac;

public:

	GrafOr();
	GrafOr(int x) { this->reSetGrOr(x); };

	int getN() { return this->n; };
	int getM() { return this->m; };

	void bfs(int x);
	void reSetGrOr(int x);
	void addDrum(int x, int y);

	vector <int> getDrumuri(int i) { return vfAdiac[i]; };

};

GrafOr::GrafOr()
{
	this->n = 0;
	this->m = 0;

	vector <int> v;
	vfAdiac.push_back(v);
}

void GrafOr::bfs(int x)
{
	ofstream g("bfs.out");
	int nrMin = 0, xInit = x, *viz = new int[this->n + 1];

	for (int i = 1; i <= this->n; i++)
		viz[i] = 0;

	viz[x] = 1;
	queue <int> qu;
	qu.push(x);

	while (!qu.empty())
	{
		nrMin++;
		x = qu.front();
		//g << x << " ";
		qu.pop();

		for (int i = 0; i < vfAdiac[x].size(); i++)
			if (!viz[vfAdiac[x][i]])
			{
				viz[vfAdiac[x][i]] = nrMin;
				qu.push(vfAdiac[x][i]);
			}
	}
	for (int i = 1; i <= this->n; i++)
		if (viz[i] == 0)
			viz[i] = -1;
	viz[x] = 0;
	for (int i = 1; i <= this->n; i++)
		g << viz[i] << " ";
	g.close();
}

void GrafOr::reSetGrOr(int x)
{
	this->n = x;
	this->m = 0;

	for (int i = 0; i < vfAdiac.size(); i++)
		vfAdiac[i].clear();
	vfAdiac.clear();

	vector <int> v;
	for (int i = 0; i <= x; i++)
		vfAdiac.push_back(v);
};

void GrafOr::addDrum(int x, int y)
{
	if (x > this->n || y > this->n || x == y)
	{
		cout << "\nEroare la adaugarea drumului\n";
		return;
	}
	for (int i = 0; i < this->vfAdiac[x].size(); i++)
		if (this->vfAdiac[x][i] == y)
			return;

	this->m++;
	this->vfAdiac[x].push_back(y);
}


int main()
{
	ifstream f("bfs.in");

	int n, m, s, x, y;
	f >> n >> m >> s;

	GrafOr graf(n);

	for (int i = 1; i <= m; i++)
	{
		cin >> x >> y;
		graf.addDrum(x, y);
	}

	graf.bfs(s);

	f.close();
	return 0;
}