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

std::vector<std::vector<int>> MakeList(std::string fisier, bool neorientat)
{
    std::ifstream file(fisier);

    if (file.is_open())
    {
        //cistesc primul rand
        std::string line;
        std::getline(file, line);
        std::stringstream ss(line);
        int noduri, muchii;
        ss >> noduri >> muchii;

        //pregatesc vectorul cu liste si variab pt nodurile muchiei
        std::vector<std::vector<int>> liste(noduri);
        int origine, destinatie;

        //constructia efectiva
        if (neorientat)
        {
            for (int i = 0; i < muchii; i++)
            {
                std::getline(file, line);
                std::stringstream ss(line);
                ss >> origine >> destinatie;
                liste[origine - 1].push_back(destinatie);
                liste[destinatie - 1].push_back(origine);
            }
        }
        else
        {
            for (int i = 0; i < muchii; i++)
            {
                std::getline(file, line);
                std::stringstream ss(line);
                ss >> origine >> destinatie;
                liste[origine - 1].push_back(destinatie);
            }
        }

        file.close();
        return liste;
    }
    else
    {
        std::cout << "!Eroare la deschiderea fisierului!\n";
        exit(1);
    }
}

std::vector<std::vector<int>> liste = MakeList("bfs.in", false);
int numNodes = liste.size();

std::vector<bool> viz(numNodes, false); // vector de vizitati
std::vector<int> tata(numNodes, 0); // vector de tati
std::vector<int> d(numNodes, -1); //vector de distante

void BFS(int s)
{
	std::queue<int> C;
	C.push(s);
	viz[s-1] = true;
	d[s-1] = 0;
	while (!C.empty())
	{
		int i = C.front();
		C.pop();
		//std::cout << i << '\n'; //afis nodul vizitat
		for (auto& j : liste[i-1])
		{
			if (!viz[j - 1])
			{
				C.push(j);
				viz[j - 1] = true;
				tata[j - 1] = i;
				d[j - 1] = d[i - 1] + 1;
			}
		}
	}
}

int main()
{
	std::ifstream in("bfs.in");
	std::ofstream out("bfs.out");

	int s;

	for (int i = 0; i < 3; i++)
	{
		in >> s;
 	}

	in.close(); //am aflat nodul de start si am inchis fisierul

	BFS(s);

	for (auto& i : d)
	{
		out << i << ' ';
	}

	out.close();

	return 0;
}