using namespace std;



#define fisier "bfs"

#ifdef fisier
    #include <fstream>
    ifstream in(fisier ".in");
    ofstream out(fisier ".out");
#else
    #include <iostream>
    #define in cin
    #define out cout
#endif



const int
MAX_N = 100000;

int de_scris[MAX_N], n, s;

#include <vector>
vector<int> de_la[MAX_N];



void bfs() {

    int coada[MAX_N];

    *coada = s;

    de_scris[s] = 1;

    for (int baza = 0, varf = 1; baza < varf; baza++) {

        //out << "coada[baza] = " << coada[baza] << endl;

        for (vector<int>::iterator vecin = de_la[coada[baza]].begin(); vecin != de_la[coada[baza]].end(); vecin++) {

            //out << "    *vecin = " << *vecin << "; de_scris[*vecin] = " << de_scris[*vecin] << endl;

            if (!de_scris[*vecin]) {

                //out << "        *vecin = " << *vecin << endl;

                de_scris[*vecin] = de_scris[coada[baza]] + 1;

                coada[varf++] = *vecin;

            }

        }

    }

}



int main() {

    int m, x, y;

    in >> n >> m >> s;
    s--;

    while (m--) {

        in >> x >> y;
        x--; y--;

        //out << "    " << x << ' ' << y << endl;
        de_la[x].push_back(y);

    }

    /*for (vector<int>::iterator it = de_la[1].begin(); it != de_la[1].end(); ++it) {

        out << *it << ' ';

    } out << endl;*/

    bfs();

    for (int i = 0; i < n; i++) {

        out << de_scris[i] - 1 << ' ';

    }

}
















//