#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <queue>

using namespace std;

void memorareGraf_listaAd(vector<set<int>> &graf_listaAd, int &N, int &M, int &S, bool graf_orientat = true){
    ifstream fin;
    fin.open("bfs.in");
    fin >> N >> M >> S;
    graf_listaAd = vector<set<int>>(N+1);
    int nod_1, nod_2;
    for(int i = 0; i < M; i++){
        fin >> nod_1 >> nod_2;
        graf_listaAd[nod_1].insert(nod_2);
        if(!graf_orientat){
            graf_listaAd[nod_2].insert(nod_1);
        }
    }
    fin.close();
}

void afisareGraf_listaAd(vector<set<int>> &graf_listaAd){
    for(int i = 1; i < graf_listaAd.size(); i++){
        cout << i << "->";
        for(auto nod: graf_listaAd[i])
            cout << nod << " ";
        cout << '\n';
    }
}

queue<int>  queque_bf;
vector<int> vc;
vector<int> cost;

void bfs(const vector<set<int>>& graf_listaAd, const int S){
    queque_bf.push(S);
    int nod_curent = S;
    vc[nod_curent] = 1;
    while(!queque_bf.empty()){
        nod_curent = queque_bf.front();
        queque_bf.pop();
//        cout << nod_curent << ' ';
        for(const int nod_vecin: graf_listaAd[nod_curent]) {
            if(vc[nod_vecin] == 0) {
                queque_bf.push(nod_vecin);
                cost[nod_vecin] = cost[nod_curent]+1;
                vc[nod_vecin] = 1;
            }
        }
    }
//    for(int i = 1; i < graf_listaAd.size(); i++)
//        if(vc[i] == 0)
//            bfs(graf_listaAd, i);
    for(int i = 1; i < graf_listaAd.size(); i++)
        if(vc[i] == 0)
            cost[i] = -1;
}

int main() {
    int N, M, S;
    vector<set<int>> graf_listaAd;
    memorareGraf_listaAd(graf_listaAd, N, M, S, true);
    cost.resize(N+1);
    vc.resize(N+1);
    for(int i = 1; i <= N; i++)
        cost[i] = vc[i] = 0;
    bfs(graf_listaAd, S);
    //cout << endl;
    for(int i = 1; i < graf_listaAd.size(); i++)
        cout << cost[i] << ' ';
    return 0;
}