#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(shared_ptr<Nod> &nodSursa) {

    queue< shared_ptr<Nod> > deVizitat;

    nodSursa->vizitat = true;
    nodSursa->distanta = 0;
    deVizitat.push(nodSursa);
    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;
        }
    }
}

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(noduri[s-1]);
    for (unsigned i = 0; i < noduri.size() - 1; ++i) {
        fout << noduri[i]->distanta << " ";
    }
    fout << noduri[noduri.size() - 1]->distanta << "\n";
    fout.close();
    return 0;
}