#include<fstream>
#include<cstdio>
using namespace std;
struct lnod{
       int info;
       struct lnod *next;
       };
typedef struct lnod cell;
typedef cell *Nod;
Nod L[100050],p; int cost[1000010],coada[1000010],i,n,m,S;      
void readdata(void);
void bf(int nod);
void scrie(void);

int main(void){
  ofstream fout("bfs.out");
  readdata();
  memset(cost,-1,sizeof(cost)); 
  bf(S);
  for(i=1;i<=n;++i)fout<<cost[i]<<' ';   
 return 0;   
}

void bf(int nod){
     int ic=1,sfc=1;
     cost[nod]=0; coada[ic]=nod; 
    while(ic<=sfc){
         p=L[coada[ic]];          
         while(p){
            if(cost[p->info]==-1){      
                 coada[++sfc]=p->info;                       
                 cost[coada[sfc]]=cost[coada[ic]]+1;                
                  }
             p=p->next;     
             }
    ++ic;        
    }
}

void readdata(void){
     ifstream fin("bfs.in");
     Nod p; int i,j,k;
     fin>>n>>m>>S;
     for(i=1;i<=n;++i)L[i]=NULL;
     for(k=1;k<=m;++k){
              fin>>i>>j;
              p=new cell;
              p->next=L[i]; p->info=j;
              L[i]=p;                                
                       }
     fin.close();         
     }