#include <iostream>
#include<fstream>
#include<stdio.h>
#include<string.h>

using namespace std;

const int LUNG = 100045;
int viz[LUNG], cat[LUNG], c[LUNG],
    n,m,start;
typedef struct nod
    {
        int inf;
        nod *adr;
    } TNOD;
TNOD *v[LUNG],*p;

void add( int a, int b )
{
    p= new TNOD;
    p->inf=a;
    p->adr=v[b];
    v[b]=p;
}

void citire()
{
    int i,x,y;
    ifstream in("bfs.in");
    in>>n>>m>>start;

    for( i=1; i<=m; i++ )
        {
            in>>x>>y;
            add(y,x);
        }
}

void bfs()
{
    int li,ls,x,size=0,j=0;
    li=ls=0;
    memset(cat,-1,sizeof(cat));
    cat[start] = 0;
    c[li++] = start;
    viz[start] = 1;


    for( ls=0; ls<=li; ls++ )
        {
            x=c[ls];
            for ( TNOD *p=v[x]; p!=0; p=p->adr )
                if( !viz[p->inf] )
                    cat[p->inf] = cat[x]+1,
                    c[li++] = p->inf,
                    viz[p->inf] = 1;
        }

    for(int i=1; i<=n; i++ )
        printf("%d ",cat[i]);

    printf("\n");
}

int main()
{

    freopen("bfs.out","w",stdout);
    citire();
    bfs();
    return 0;
}