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

ifstream f("bfs.in");
ofstream g("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) {
    vector<int> niveluri(nr_noduri + 1, -1); // Folosim un vector pentru a stoca nivelurile

    queue<Nod*> coada;
    coada.push(radacina);

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

        if (!nodCurent->vizitat) {
            for (const auto& muchie : muchii) {
                if (muchie.first == nodCurent->valoare) {
                    int fiuValoare = muchie.second;
                    if (niveluri[fiuValoare] == -1) {
                        Nod* fiu = new Nod;
                        fiu->valoare = fiuValoare;
                        fiu->nivel = nodCurent->nivel + 1;
                        fiu->vizitat = false;
                        nodCurent->fii.push_back(fiu);
                        coada.push(fiu);
                        niveluri[fiuValoare] = fiu->nivel;
                    }
                }
            }
            nodCurent->vizitat = true;
        }
    }

    for (int i = 1; i <= nr_noduri; i++) {
        g << niveluri[i] << " ";
    }
}

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;
}