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

using namespace std;

vector<int> calculeazaDistanteLaToateNodurileDeLaNodul(
        int nodSursa, vector< list<int> > &listeAdiacenta) {

    int n = listeAdiacenta.size() - 1;
    vector<int> distante(n+1, -1);
    vector<bool> vizitate(n+1, false);
    queue<int> deVizitat;

    deVizitat.push(nodSursa);
    vizitate[nodSursa] = true;
    distante[nodSursa] = 0;
    while (!deVizitat.empty()) {
        int nodCurent = deVizitat.front();
        deVizitat.pop();
        list<int>::iterator it;
        it = listeAdiacenta[nodCurent].begin();
        while (it != listeAdiacenta[nodCurent].end()) {
            if (!vizitate[*it]) {
                vizitate[*it] = true;
                deVizitat.push(*it);
                distante[*it] = distante[nodCurent] + 1;
            }
            ++it;
        }
    }

    return distante;
}

int main() {
    ifstream fin("bfs.in");
    int n, m, s;
    fin >> n >> m >> s;
    vector< list<int> > listeAdiacenta(n+1);
    unsigned i = 1;
    while (i <= m) {
        int x, y;
        fin >> x;
        fin >> y;
        listeAdiacenta[x].push_back(y);
        i += 1;
    }

    ofstream fout("bfs.out");
    vector<int> distante;
    distante = calculeazaDistanteLaToateNodurileDeLaNodul(s, listeAdiacenta);
    for (int i = 1; i < distante.size() - 1; ++i) {
        fout << distante[i] << " ";
    }
    fout << distante[distante.size() - 1] << "\n";
/*    i = 1;
    list<int>::iterator it;
    while(i < listeAdiacenta.size()) {
        it = listeAdiacenta[i].begin();
        while (it != listeAdiacenta[i].end()) {
            fout << i << " " << *it << "\n";
            ++it;
        }
        i += 1;
 */
    fout.close();
    return 0;
}