#include <fstream>
#include <vector>
#include <queue>

#define maxi 100001

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

class Graf {
    int nrNoduri, nrMuchii;
    int vizitat2[maxi];
//    coada[maxi];
    int pozitiePlecare, pozitieUltima;
    vector<int> *adiacenta; // lista de vecini
    queue<int> coada;
public:
    Graf();

    void citireBFS(int &nodPlecare);

    void BFS(int nodPlecare);

    void afisareCoada2();

    ~Graf();
};

void Graf::citireBFS(int &nodPlecare) {
    int x, y;
    fin >> nrNoduri >> nrMuchii >> nodPlecare;
    for (int i = 1; i <= nrMuchii; i++) {
        fin >> x >> y;
        adiacenta[x].push_back(y);
    }
//    coada = new int [maxi];
//    vizitat2 = new int [maxi];
    coada.push(nodPlecare);
//    coada[1] = nodPlecare;
//    vizitat2[coada[1]] = 1;
    vizitat2[coada.back()] = 1;
}

void Graf::BFS(int pozitiePlecare) {
    int nodPlecare = coada.front();
//    int nodPlecare = coada[pozitiePlecare]; // retin nodul de unde plec
    for (int j = 0; j < adiacenta[nodPlecare].size(); j++)
        if (vizitat2[adiacenta[nodPlecare][j]] == -1) {
            // caut toate nodurile nevizitate care sunt adiacente cu nodul de plecare
            vizitat2[adiacenta[nodPlecare][j]] = vizitat2[nodPlecare] + 1; // il marcam vizitat
            pozitieUltima++; // indexez pozitia ultimului element din coada
//            coada[pozitieUltima] = adiacenta[nodPlecare][j]; // il adaug in coada PUSH
            coada.push(adiacenta[nodPlecare][j]);
        }
    if (pozitiePlecare < pozitieUltima) // daca mai sunt elemente in coada / nu am verificat pt toate nodurile
    {
        coada.pop();
        BFS(pozitiePlecare + 1);
    }
}

void Graf::afisareCoada2() {
    for (int i = 1; i <= nrNoduri; i++) {
        if (vizitat2[i] != -1)
            fout << vizitat2[i] - 1 << " ";
        else
            fout << -1 << " ";
    }
}

int main() {
    int nodPlecare;
    Graf g1;
    g1.citireBFS(nodPlecare);
    g1.BFS(1);
    g1.afisareCoada2();

    fin.close();
    fout.close();
    return 0;
}

// neorientat
Graf::Graf() {
    adiacenta = new vector<int>[maxi];
    for (int i = 1; i <= maxi; i++)
        vizitat2[i] = -1;
    pozitiePlecare = pozitieUltima = 1;
}

Graf::~Graf() {
    delete[] adiacenta;
}