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

using namespace std;

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

class Graf
{
private:

	int nrMuchii, nrNoduri;
	vector<vector<int>> listaAdiacenta;
	bool orientat;

	void adaugaMuchie(int, int, bool);


public:
	Graf();
	Graf(int, int, bool);
	void BFS(int);

};

Graf::Graf()
{
	nrMuchii = 0;
	nrNoduri = 0;
	orientat = false;
}

Graf::Graf(int n, int m, bool orr)
{
	int x, y;

	nrNoduri = n;
	nrMuchii = m;
	orientat = orr;
	listaAdiacenta.resize(nrNoduri + 1);

	for (int i = 0; i < nrMuchii; i++)
	{
		fin >> x >> y;
		listaAdiacenta[x].push_back(y);
		if (!orr)
		{
			listaAdiacenta[y].push_back(x);
		}
	}
}

void Graf::adaugaMuchie(int n1, int n2, bool orr)
{
	listaAdiacenta[n1].push_back(n2);
	if (!orr)
	{
		listaAdiacenta[n2].push_back(n1);
	}
}

void Graf::BFS(int nodStart)
{
	queue<int> q;
	vector<bool> vizitate(nrNoduri+1, false);
	vector<int> distante(nrNoduri+1, -1);

	q.push(nodStart);

	vizitate[nodStart] = true;
	distante[nodStart] = 0;

	while (!q.empty())
	{
		int nodCurent = q.front();
		q.pop();

		for (int nodVecin : listaAdiacenta[nodCurent])
		{
			if (!vizitate[nodVecin])
			{
				vizitate[nodVecin] = true;
				q.push(nodVecin);
				distante[nodVecin] = distante[nodCurent] + 1;
			}
		}
	}

	for (int i=1; i<distante.size();i++)
	{
		fout << distante[i] << ' ';
	}
}


int main()
{
	int n, m, s;
	fin >> n >> m >> s;

	Graf G(n, m, true);

	G.BFS(s);

	return 0;
}