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

void 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()) {
            shared_ptr<Nod> nodIteratie1 = *nodIteratie;
            if (!nodIteratie1->vizitat) {
                nodIteratie1->vizitat = true;
                nodIteratie1->distanta = nodCurent->distanta + 1;
                deVizitat.push(nodIteratie1);
            }
            ++nodIteratie;
        }
    }
}

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);
    }
    int i = 0;
    while (i < m) {
        int x, y;
        fin >> x;
        fin >> y;
        noduri[x-1]->noduriAdiacente.push_back(noduri[y-1]);
        i += 1;
    }
    fin.close();

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