#include <fstream>
#include <list>
#include <vector>
//#include <queue>

int main(){
    std::ifstream fin("bfs.in");
    std::ofstream fout("bfs.out");

    unsigned N,M,S;
    fin>>N>>M>>S;
    std::vector< std::list<unsigned> > liste(M);
    for(unsigned i=0;i<M;++i){
        unsigned a,b;
        fin>>a>>b;
        if(b!=S) liste[a-1].push_back(b-1);
    }

    std::vector<int> cost(N,-1);
    //std::queue<unsigned> sor;
    std::vector<unsigned> sor(N);
    unsigned bind=0,peind=0;

    cost[S-1]=0;
    //sor.push(S-1);
    sor[peind]=S-1; peind++;

    while(/* !sor.empty()*/ bind<peind){
        //S=sor.front(); sor.pop();
        S=sor[bind]; bind++;
        for(;!liste[S].empty();liste[S].pop_front()){
            M=liste[S].front();
            if(cost[M]==-1){
                cost[M]=cost[S]+1;
                //sor.push(M);
                sor[peind]=M; peind++;
            }
        }
    }

    for(unsigned i=0;i<N;++i) fout<<cost[i]<<' ';
    fout<<'\n';
}