#include <fstream>
#include <vector>
#include <list>
#include <queue>
#include <iterator>
#include <memory>

using namespace std;

struct Nod {
    const int id;
    int distanta;
    bool vizitat;
    list< shared_ptr<Nod> > noduriAdiacente;

    Nod (int id) : id(id){
        distanta = -1;
        vizitat = false;
    }
};

vector<int> calculeazaDistanteLaToateNodurileDeLaNodul(
        int idNodSursa, const vector< shared_ptr<Nod> > &noduri) {

    queue< shared_ptr<Nod> > deVizitat;

    --idNodSursa;
    noduri[idNodSursa]->vizitat = true;
    noduri[idNodSursa]->distanta = 0;
    deVizitat.push(noduri[idNodSursa]);
    while (!deVizitat.empty()) {
        shared_ptr<Nod> nodCurent = deVizitat.front();
        deVizitat.pop();
        list< shared_ptr<Nod> >::iterator nodIteratie;
        nodIteratie = nodCurent->noduriAdiacente.begin();
        while (nodIteratie != nodCurent->noduriAdiacente.end()) {
            if (!(*nodIteratie)->vizitat) {
                (*nodIteratie)->vizitat = true;
                (*nodIteratie)->distanta = nodCurent->distanta + 1;
                deVizitat.push(*nodIteratie);
            }
            ++nodIteratie;
        }
    }

    vector<int> distante(noduri.size()+1);
    for (unsigned i = 0; i < noduri.size(); ++i) {
        distante[noduri[i]->id] = noduri[i]->distanta;
    }

    return distante;
}

int main() {
    ifstream fin("bfs.in");
    int n, m, s;
    fin >> n >> m >> s;
    vector< shared_ptr<Nod> > noduri(n);
    for (unsigned i = 0; i < noduri.size(); ++i) {
        noduri[i] = make_shared<Nod> (i+1);
    }
    unsigned i = 0;
    while (i < m) {
        int x, y;
        fin >> x;
        fin >> y;
        noduri[x-1]->noduriAdiacente.push_back(noduri[y-1]);
        i += 1;
    }

    ofstream fout("bfs.out");
    vector<int> distante;
    distante = calculeazaDistanteLaToateNodurileDeLaNodul(s, noduri);
    for (unsigned i = 1; i < distante.size() - 1; ++i) {
        fout << distante[i] << " ";
    }
    fout << distante[distante.size() - 1] << "\n";
    fout.close();
    return 0;
}