#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 minEdgeBFS(int u);
	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::minEdgeBFS(int u)
{
	ofstream g("bfs.out");
	bool *visited = new bool[n + 1];
	for (int i = 1; i <= n; i++)
		visited[i] = 0;

	int *distance = new int[n + 1];
	for (int i = 1; i <= n; i++)
		distance[i] = 0;

	queue <int> Q;
	distance[u] = 0;

	Q.push(u);
	visited[u] = true;
	while (!Q.empty())
	{
		int x = Q.front();
		Q.pop();

		for (int i = 0; i < vfAdiac[x].size(); i++)
		{
			if (visited[vfAdiac[x][i]])
				continue;

			distance[vfAdiac[x][i]] = distance[x] + 1;
			Q.push(vfAdiac[x][i]);
			visited[vfAdiac[x][i]] = 1;
		}
	}
	for (int i = 1; i <= n; i++)
		if (distance[i] == 0)
			distance[i] = -1;
	distance[u] = 0;
	for (int i = 1; i <= n; i++)
		g << distance[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++)
	{
		f >> x >> y;
		graf.addDrum(x, y);
	}
	graf.minEdgeBFS(s);

	f.close();
	
	return 0;
}