/* 
 * File:   bsf.c
 * Author: slycer
 *
 * Created on February 27, 2011, 11:02 PM
 */

#include <stdio.h>
#include <stdlib.h>

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

/*
 * 
 */
int main(int argc, char** argv) {

    FILE * in = fopen("bsf.in","r");
    FILE * out = fopen("bsf.out","w"); 
    
    int n,m,start; 
    fscanf(in,"%d%d%d",&n,&m,&start);
    
    struct nod * t = calloc( n+1,sizeof( struct nod )); 
    
    int i; 
    for ( i=0; i<m; i++){
        int x,y; 
        fscanf(in,"%d%d",&x,&y);
        struct nod *nou = calloc(1,sizeof( struct nod )); 
        nou->next = t[x].next; 
        nou->x = y; 
        t[x].next = nou; 
    }
    
    int * queue = calloc(n+1,sizeof(int)); 
    int * marcat = calloc(n+1, sizeof(int));
    int * drum = calloc(n+1, sizeof(int)); 
    
    for ( i=1; i<=n; i++){
        drum[i] = -1; 
    }
    
    int left = 0; 
    int right = 0; 
    
    marcat[start] = 1; 
    queue[left]=start; 
    drum[start]=0; 
    
/*
    while ( left<=right){
        int nod = queue[left++]; 
       // printf("%d\n",nod); 
        struct nod * current ;//= t[nod].next; 
        for (current = t[nod].next; current!=NULL; current=current->next){
            if ( !marcat [ current->x ]){
               marcat[current->x] = 1; 
               queue[++right ] = current->x;
               drum[ current->x] = drum[nod]+1; 
            }
        }
    }
*/
    
    for ( i=1; i<=n; i++){
        fprintf(out,"%d ",drum[i]); 
    }
    
    fclose( in ); 
    fclose( out ); 
    
    return (EXIT_SUCCESS);
}