#include <fstream>
#include <deque>
#include <vector>
using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

int main(){
    int N, M, S;
    fin >> N >> M >> S;
    int n1, n2;

    vector<int> A[N+1];

    for (int i = 0; i < M; i++) {
        fin >> n1 >> n2;
        A[n1].push_back(n2);
    }

    deque<int> deq;

    vector<int> arce(N+1, -1);
    arce[S] = 0;
    deq.push_back(S);

    while (!deq.empty()) {
        int curent = deq.front();
        deq.pop_front();

        for (int nod : A[curent]) {
            if (arce[nod] == -1) {
                arce[nod] = arce[curent] + 1;
                deq.push_back(nod);
            }
        }
    }

    for (int i = 1; i <= N; i++) {
        fout << arce[i] << " ";
    }
    
    return 0;
}