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 << 'b' << coada[baza] << endl;

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

            //out << "    v" << *vecin << ' ' << de_scris[*vecin] << endl;

            if (!de_scris[*vecin]) {

                //out << "        " << *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--;

        de_la[x].push_back(y);

    }

    bfs();

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

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

    }

}
















//