#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <map>
using namespace std;

ifstream f("C:\\Users\\User\\CLionProjects\\AN2-AF\\BFS\\bfs.in");
ofstream g("C:\\Users\\User\\CLionProjects\\AN2-AF\\BFS\\bfs.out");

struct Nod {
    int valoare;
    vector<Nod*> fii;
    bool vizitat;
    int nivel;
};

void BFS(Nod* radacina, const vector<pair<int, int>>& muchii, int nr_noduri) {
    map<int,int> niveluri;
    for(int i=1;i<=nr_noduri;i++)
        niveluri[i] = -1;
    queue<Nod*> coada;
    vector<Nod*> vizite;
    coada.push(radacina);

    while (!coada.empty()) {
        Nod* nodCurent = coada.front();
        vizite.push_back(nodCurent);
        coada.pop();


        if(!nodCurent->vizitat){
            for (const auto& muchie : muchii) {
                if (muchie.first == nodCurent->valoare) {
                    bool ok = false;
                    for(auto element: vizite)
                        if(element->valoare == muchie.second)
                            ok = true;

                    if (!ok)
                    {
                        Nod *fiu = new Nod;
                        fiu->valoare = muchie.second;
                        fiu->nivel = nodCurent->nivel + 1;
                        fiu->vizitat = false;
                        nodCurent->fii.push_back(fiu);
                        coada.push(fiu);
                    }

                }

            }
            niveluri[nodCurent->valoare] = nodCurent->nivel;
            nodCurent->vizitat = true;

        }
    }

    for(auto element:niveluri)
        g << element.second << " ";


}

int main() {
    int nr_noduri, nr_muchii, radacina, aux1, aux2;
    vector<pair<int, int>> muchii;
    f >> nr_noduri >> nr_muchii >> radacina;
    while (f >> aux1) {
        f >> aux2;
        muchii.emplace_back(aux1, aux2);
    }

    Nod* radacinaNod = new Nod;
    radacinaNod->valoare = radacina;
    radacinaNod->vizitat = false;
    radacinaNod->nivel = 0;

    BFS(radacinaNod, muchii,nr_noduri);

    queue<Nod*> coada;
    coada.push(radacinaNod);
    while (!coada.empty()) {
        delete coada.front();
        coada.pop();
    }

    return 0;
}