//ALEX ENACHE

#include <fstream>
#include <vector>
#include <queue>

using namespace std;

//ifstream cin("input"); ofstream cout("output");
ifstream cin("bfs.in"); ofstream cout("bfs.out");

vector<vector<int>> gr; //lista de adiacenta
vector<bool> folosit; //marcam daca am trecut deja
vector<int> distanta; //distanta de la sursa la nod
queue<int> q; //coada ca la lee cu indicele nodului

int main() {

    int n, m, s;
    cin>>n>>m>>s;

    gr.resize(n+1);
    folosit.resize(n+1, false);
    distanta.resize(n+1, -1);

    int a, b;
    for (int i=1; i<=m; i++){
        cin>>a>>b;
        gr[a].push_back(b); //am muchie de la a la b -> adaug in lista vecinilor lui a pe b
    }

    folosit[s] = true;
    distanta[s] = 0;
    q.push(s);

    while(!q.empty()){
        int nodCurent = q.front(); // ne scoatem nodul curent din coada
        q.pop();

        for (auto &vecin : gr[nodCurent]){ // mergem in toti vecinii nodului curent
            if (!folosit[vecin]){
                folosit[vecin] = true;
                distanta[vecin] = distanta[nodCurent] + 1;
                q.push(vecin); //adaugam vecinul in coada
            }
        }
    }

    for (int i=1; i<=n; i++){
        cout<<distanta[i]<<" ";
    }
    cout<<'\n';

    return 0;
}