#include <iostream>
#include <list>
#include <fstream>
#include <stack>

using namespace std;

// ifstream fin("input.txt");
// ofstream fout("output.txt");

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


class graf {
private:
    int n;
    list<int> *ad;

public:
    graf(int n=1) {
        this->n = n;
        this->ad = new list<int>[n];
    };

    void adaug_muchie(int v, int w) {
        this->ad[v].push_back(w); 
    };

    void BFS(int s);
    void distante(int s);
    void DFS(int s);
    void recursiv(int s, bool *vizitat);
};

void graf::BFS(int s) {
    bool *vizitat = new bool[n];
    for (int i = 0; i < n; i++) {
        vizitat[i] = false;
    }

    list<int> coada;
    vizitat[s] = true;
    coada.push_back(s);

    while(!coada.empty()) {
        list<int>::iterator i;

        s = coada.front();
        fout << s << " ";
        // fout << s+1 << " ";

        coada.pop_front();

        for (i = ad[s].begin(); i != ad[s].end(); i++) {
            if (vizitat[*i] == false) {
                vizitat[*i] = true;
                coada.push_back(*i);
            }
        }
    }
    delete[] vizitat;
}

void graf::distante(int s) {
    bool *vizitat = new bool[n];
    int *distante = new int[n];
    for (int i = 0; i < n; i++) {
        vizitat[i] = false;
        distante[i] = -1;
    }

    list<int> coada;
    vizitat[s] = true;
    coada.push_back(s);
    distante[s] = 0;

    while(!coada.empty()) {
        list<int>::iterator i;

        s = coada.front();
        coada.pop_front();

        for (i = ad[s].begin(); i != ad[s].end(); i++) {
            if (vizitat[*i] == false) {
                vizitat[*i] = true;
                distante[*i] = distante[s] + 1;
                coada.push_back(*i);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        fout << distante[i] << " ";
    }

    delete[] vizitat;
    delete[] distante;
}

void graf::DFS(int s) {
    bool *vizitat = new bool[n];
    for (int i = 0; i < n; i++) {
        vizitat[i] = false;
    }

    recursiv(s, vizitat);
    delete[] vizitat;
}

void graf::recursiv(int s, bool *vizitat) {
    vizitat[s] = true;
    fout << s << " ";

    list<int>::iterator it;

    for (it = ad[s].begin(); it != ad[s].end(); it++) {
        if (!vizitat[*it])
            recursiv(*it, vizitat);
    }
}


int main() {
    int n, m, s, a, b;
    fin >> n >> m >> s;
    graf g(n);

    for (int i = 0; i < m; i++) {
        fin >> a >> b;
        g.adaug_muchie(a-1, b-1);
    }

    g.distante(s-1);
    return 0;
}