#include<fstream>
#define maxn 100001
using namespace std;
ifstream fi("bfs.in");
ofstream fo("bfs.out");

struct nod{
       int info;
       nod *next;
       };

int d[maxn],c[maxn];
int i,n,m,s,x,y; 
nod *a[maxn],*q;

void bfs(int s){
     int i,k;
     
     c[1]=s; i=1; k=1;
     while(i<=k)
      {
       q=a[c[i]];
       while(q!=NULL){
                      if(d[q->info]==-1) {
                                         c[++k]=q->info;
                                         d[c[k]]=d[c[i]]+1;
                                        }
                      q=q->next;
                     }
       i++;
      } 
}

int main(){
    fi>>n>>m>>s;
    
    for(i=1;i<=n;i++) { d[i]=-1; a[i]=NULL; }
    
    for(i=1;i<=m;i++){
                      fi>>x>>y; 
                      q=new nod; 
                      q->info=y; 
                      q->next=a[x]; 
                      a[x]=q;
                     }
    d[s]=0; 
    bfs(s);
    
    for(i=1;i<=n;i++) fo<<d[i]<<" ";
    
    fi.close();
    fo.close();
    return 0;
}