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

using namespace std;

struct Nod {
    int distanta;
    bool vizitat;
    list<int> idNoduriAdiacente;

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

void viziteazaNod(int idNod, int idNodSursa, vector<Nod> &noduri) {
    noduri[idNod].vizitat = true;
    noduri[idNod].distanta = noduri[idNodSursa].distanta + 1;
}

void viziteazaNodurileAdiacenteNodului(int idNod, vector<Nod> &noduri,
        queue<int> &deVizitat) {

    list<int>::iterator idNodIteratie;
    idNodIteratie = noduri[idNod].idNoduriAdiacente.begin();
    while (idNodIteratie != noduri[idNod].idNoduriAdiacente.end()) {
        if (!noduri[*idNodIteratie].vizitat) {
            viziteazaNod(*idNodIteratie, idNod, noduri);
            deVizitat.push(*idNodIteratie);
        }
        ++idNodIteratie;
    }
}

void calculeazaDistanteleLaToateNodurileDeLaNodul(int idNodSursa,
       vector<Nod> &noduri) {

    queue<int> deVizitat;
    noduri[idNodSursa].vizitat = true;
    noduri[idNodSursa].distanta = 0;
    deVizitat.push(idNodSursa);
    while (!deVizitat.empty()) {
        int idNodCurent = deVizitat.front();
        deVizitat.pop();
        viziteazaNodurileAdiacenteNodului(idNodCurent, noduri, deVizitat);
    }
}

int main() {
    ifstream fin("bfs.in");
    int n, m, s;
    fin >> n >> m >> s;
    vector<Nod> noduri(n+1);
    int i = 0;
    while (i < m) {
        int x, y;
        fin >> x;
        fin >> y;
        noduri[x].idNoduriAdiacente.push_back(y);
        i += 1;
    }
    fin.close();

    ofstream fout("bfs.out");
    calculeazaDistanteleLaToateNodurileDeLaNodul(s, noduri);
    for (unsigned i = 1; i < noduri.size() - 1; ++i) {
        fout << noduri[i].distanta << " ";
    }
    fout << noduri[noduri.size() - 1].distanta << "\n";
    fout.close();
}