#include <bits/stdc++.h>
#include<fstream>
#include<vector>
#include<map>
#include<queue>
std::ifstream f("bfs.in");
std::ofstream fg("bfs.out");
int n, m, a, b, s;

class graf{
public:
    int n, m;
    graf(int n, int m);

    std::map<int, bool> viz;
    std::map<int, std::vector<int> > lista;
    std::vector<int> dist;

    void new_lista( int nod1, int nod2);
    void afisare_lista();

    void bfs(int nod);
};

graf::graf(int n, int m) {
    this->n = n;
    this->m = m;
}

void graf::new_lista(int nod1, int nod2){
    lista[nod1].push_back(nod2);
}

void graf::afisare_lista() {
    for(auto i=1 ; i<n+1 ; i++){
        std::cout<<i<<" : ";
        for(auto j=0 ; j<lista[i].size(); j++)
            std::cout<<lista[i][j]<<" ";
        std::cout<<"\n";
    }
}
void graf::bfs(int nod){
    for(auto i = 0 ; i<=n ; i++){
        viz[i] = false;
        dist.push_back(-1);
    }

    std::queue<int> coada;

    viz[nod] = true;
    dist[nod] = 0;
    coada.push(nod);

    while(!coada.empty()){
        int vecin = coada.front();
        //std::cout<<vecin<<" ";
        coada.pop();

        for( auto i = lista[vecin].begin() ; i != lista[vecin].end(); i++){
            if( !viz[*i] ){
                viz[*i] = true;
                coada.push(*i);
                dist[*i] = dist[vecin] + 1;
            }
        }
    }

    //std::cout<<"\n";
    for(int i = 1; i <= n; i++)
        fg<<dist[i]<<" ";

}

int main() {
    f>>n>>m>>s;

    graf g(n, m);
    for(int i=0 ; i<m ; i++){
        f>>a>>b;
        g.new_lista(a,b);
    }

    g.bfs(s);
    return 0;
}