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

//std::ifstream f("graful.txt");
//std::ofstream g("graful.out");
std::ifstream f("bfs.in");
std::ofstream g("bfs.out");

int start = 0;
class graf
{
	int nrvf, nrmuchii;
	//std::unordered_map < int, std::vector< int > > vecini;
	std::vector<int>* vecini;

public:
	//void creaza_muchie(int start, int finish);

	graf(bool orientat);

	void verifvecini();

	void BFS();

	~graf()
	{
		delete []vecini;
	}
};

//void graf::creaza_muchie(int start, int finish)
//{
//	if (vecini.find(start) != vecini.end())
//		vecini[start].push_back(finish);
//	else
//	{
//		std::vector < int > vaux;
//		vaux.push_back(finish);
//		std::pair < int, std::vector < int > > paux(start, vaux);
//		vecini.insert(paux);
//	}
//}

graf::graf(bool orientat)
{
	f >> nrvf >> nrmuchii;
	if(start == 1)	// daca avem de citit un nod de start...
		f >> start;

	//if (orientat == true)
	//	for (int i = 0; i < nrmuchii; i++)
	//	{
	//		int x, y;
	//		f >> x >> y;
	//		creaza_muchie(x, y);
	//	}
	//else
	//	for (int i = 0; i < nrmuchii; i++)
	//	{
	//		int x, y;
	//		f >> x >> y;
	//		creaza_muchie(x, y);
	//		creaza_muchie(y, x);
	//	}

	vecini = new std::vector<int>[nrvf + 1];
	if (orientat == true)
		for (int i = 0; i < nrmuchii; i++)
		{
			int x, y;
			f >> x >> y;
			vecini[x].push_back(y);
		}
	else
		for (int i = 0; i < nrmuchii; i++)
		{
			int x, y;
			f >> x >> y;
			vecini[x].push_back(y);
			vecini[y].push_back(x);
		}
}

void graf::verifvecini()
{
	for (int i = 1; i <= nrvf; i++)
	{
		std::cout << "\n  vecinii lui " << i << " :  ";
		for (unsigned int j = 0; j < vecini[i].size(); j++)
			std::cout << vecini[i][j] << " ";
	}
}

void graf::BFS()
{
	int* dist = new int[nrvf + 1]{ 0 };	// initializam distantele cu 0 (le decrementam ulterior)
	std::queue <int> qBFS;	  // coada pt BFS
	qBFS.push(start);
	dist[start] = 1;

	while (!qBFS.empty())
	{
		const int nod = qBFS.front();
		for (unsigned int i = 0; i < vecini[nod].size(); i++)
		{
			const int nod_urm = vecini[nod][i];
			if (dist[nod_urm] == 0)
			{
				qBFS.push(nod_urm);
				dist[nod_urm] = dist[nod] + 1;
			}
		}

		qBFS.pop();
	}

	for (int i = 1; i <= nrvf; i++)
		g << dist[i] - 1 << " ";

	delete [] dist;
}

int main()
{
	start = 1;		// afirmam ca citim si un nod de start;
	graf g(true);
	//g.verifvecini();
	
	g.BFS();

	return 0;
}