# include <fstream>
# define DIM 100010
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
struct List{
    int val;
    List *next;
};
List *first[DIM],*last[DIM],*cfirst,*clast;
int Marcat[DIM],n,m,i,x,y,ns;
void push_back(int x,int y){
    if(first[x]==NULL){
        first[x]=new List;
        first[x]->val=y;
        first[x]->next=NULL;
        last[x]=first[x];
        return;
    }
    List *p;
    p=new List;
    p->val=y;
    p->next=NULL;
    last[x]->next=p;
    last[x]=p;
    return;
}
void cpush_back(int x){
    if(cfirst==NULL){
        cfirst=new List;
        cfirst->val=x;
        cfirst->next=NULL;
        clast=cfirst;
        return;
    }
    List *p;
    p=new List;
    p->val=x;
    p->next=NULL;
    clast->next=p;
    clast=p;
    return;
}
void cpop_front(){
    List *p;
    p=cfirst->next;
    delete cfirst;
    cfirst=p;
}
void bfs(int ns){
    cpush_back(ns);
    Marcat[ns]=1;
    while(cfirst!=NULL){
        int nc=cfirst->val;
        cpop_front();
        List *p;
        p=first[nc];
        while(p!=NULL){
            int nv=p->val;
            if(!Marcat[nv]){
                Marcat[nv]=Marcat[nc]+1;
                cpush_back(nv);
            }
            p=p->next;
        }
    }
}
int main () {
    fin>>n>>m>>ns;
    for(i=1;i<=m;i++){
        fin>>x>>y;
        push_back(x,y);
    }
    bfs(ns);
    for(i=1;i<=n;i++)
        fout<<Marcat[i]-1<<" ";
    fout<<"\n";
    return 0;
}