#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);		//Am decis sa fac adaugarea unei muchii in lista de adiacenta o functie, poate o sa fie useful later?


public:
	Graf();
	Graf(int, int, bool);
	void BFS(int);							//Functie care rezolva problema BFS de pe infoarena

};

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);	//Construim si reprezentarea grafului in constructor

	for (int i = 0; i < nrMuchii; i++)
	{
		fin >> x >> y;
		adaugaMuchie(x, y, orientat);
	}
}

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 de bool initializat cu false, in el vom retine daca nodurile au fost vizitate
	vector<int> distante(nrNoduri+1, -1);			//vector de int care retine distantele de la nodul de start, initializat cu -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;			//BFS normal, iar in if() calculam si distanta dintre nodul curent si nodul de start
				q.push(nodVecin);					//Distanta creste cu 1 de fiecare data cand trecem de la un nod la altul
				distante[nodVecin] = distante[nodCurent] + 1;
			}
		}
	}

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


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

	Graf G(n, m, true);

	G.BFS(s);

	return 0;
}