#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
std::ifstream fin("bfs.in");
std::ofstream fout("bfs.out");
void bfs(int i,std::vector<std::vector<int>>&lista,std::vector<int> &dis,std::vector<bool> & viz,std::queue<int> q,int nr){
    viz[i]=true;
    dis[i]=nr;
    q.push(i);
    while(!q.empty()){
        int nod_curent=q.front();
        q.pop();
        std::cout<<nod_curent<<" ";
        for(int j=0;j<lista[nod_curent].size();j++){
            if(viz[lista[nod_curent][j]]==0){
                q.push(lista[nod_curent][j]);
                viz[lista[nod_curent][j]]=true;
                dis[lista[nod_curent][j]]=dis[nod_curent]+1;
            }
        }
    }
}
int main(){
    int n,m,s,x,y;
    fin>>n>>m>>s;
    std::vector<std::vector<int>> lista(n+1);
    std::queue<int> q;
    std::vector<int> dis(n+1);
    std::vector<bool> viz(n+1);
    for(int i=1;i<=n;i++){
        dis[i]=-1;
    }
    dis[s]=0;
    while(m){
        fin>>x>>y;
        if(x!=y){
            lista[x].push_back(y);
        }
        m--;
    }
    bfs(s,lista,dis,viz,q,0);
    for(int i=1;i<=n;i++){
        fout<<dis[i]<<" ";
    }
}