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

using namespace std;

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

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

void calculeazaDistanteLaToateNodurileDeLaNodul(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();
        list<int>::iterator idNodIteratie;
        idNodIteratie = noduri[idNodCurent].idNoduriAdiacente.begin();
        while (idNodIteratie != noduri[idNodCurent].idNoduriAdiacente.end()) {
            if (!noduri[(*idNodIteratie)].vizitat) {
                noduri[(*idNodIteratie)].vizitat = true;
                noduri[(*idNodIteratie)].distanta = noduri[idNodCurent].distanta + 1;
                deVizitat.push(*idNodIteratie);
            }
            ++idNodIteratie;
        }
    }
}

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