#include <bits/stdc++.h>
using namespace std;

void BFS(int s, vector<vector<int>> &listaVecini, vector<int> &distanta){
    vector<int> vizitat (listaVecini.size(), 0);
    queue<int> coada;

    vizitat[s - 1] = 1;
    coada.push(s);

    while(coada.empty() == false){
        int nod = coada.front();
        //cout << nod;
        coada.pop();

        for (int i = 0 ; i < listaVecini[nod - 1].size(); i++){
            if (vizitat[listaVecini[nod - 1][i] - 1] == 0){
                vizitat[listaVecini[nod - 1][i] - 1] = 1;
                coada.push(listaVecini[nod - 1][i]);
                distanta[listaVecini[nod - 1][i] - 1] = distanta[nod - 1] + 1;
            }
        }
    }

}


int main(){
    ifstream f("bfs.in");
    ofstream g("bfs.out");

    int n, m, s, muchie1, muchie2;
    vector<vector<int>> listaVecini;

    f >> n >> m >> s;

    vector<int> distanta (n , 0);

    for (int i = 0; i < n; i++){
        vector<int> aux = {};
        listaVecini.push_back(aux);
    }

    for (int i = 0; i < m ; i++){
        f >> muchie1;
        f >> muchie2;
        listaVecini[muchie1 - 1].push_back(muchie2);
    }

    BFS(s, listaVecini, distanta);

    for (int i = 0 ; i < n; i++){
        g << distanta[i] << " ";
   }

    return 0;
}