#include <iostream>
#include <fstream>
using namespace std;

const int maxn = 100000;
const int maxm = 1000000;
int N, M, S;

ifstream f( "bfs.in");
ofstream g( "bfs.out");

typedef struct l_nod
{
    int nod;
    l_nod* leg;
} nod;

typedef struct coada
{
    int nod;
    coada* next;
    coada* prev;
} e_q;

e_q* mq = NULL;
e_q* current;

void adauga_in_q(int x);
int sterge_din_q();

nod* lista[ maxn ];
int viz[maxn];
int cost[maxn];

void citeste();
void adauga( int x , int y );

void BFS( int start);


int main()
{
    citeste();
    BFS(S);
    for( int i = 1 ; i <= N ; i++ )
    {
        if ( viz[i] == 0  && i!= S  )
            g << -1 << " " ;
        else
            g << cost[i] << " " ;
    }
    return 0;
}

void BFS( int start )
{
    int x;
    adauga_in_q( start );
    viz[start] = 1;
    cost[start] = 0;
    nod* aux;

    while( mq )
    {
       x = sterge_din_q();
       if(  lista[x] == 0 )
       {
           continue;
       }
       else
       {
          aux = lista[ x ];
          while( aux )
               {
                   if( !viz[ aux->nod ] )
                   {
                       adauga_in_q( aux->nod);
                       cost[ aux->nod ] = 1 + cost[ x];
                       viz[ aux->nod ] = 1;
                   }

                   aux = aux->leg;
               }
       }
    }
}

void adauga(int x, int y )
{
    nod* aux =  new nod;
    aux->nod = y;
    aux->leg = lista[ x ];
    lista[ x ] = aux;
}

void citeste()
{
    int x, y;
    f >> N >> M >> S;
    while( f >> x >> y  )
    adauga( x, y );
}

void adauga_in_q(int x)
{
    e_q* nou = new e_q;
    nou->nod = x;
    nou->next = NULL;
    nou->prev = NULL;
    if ( mq == NULL )
    {
        mq = nou;
        current = mq;
    }

    else
    {
        current->next = nou;
        nou->prev = current;
        current = current->next;
    }
}

int  sterge_din_q()
{
    e_q* aux;
    int rezultat = 0;
    if ( mq == NULL)
        return 0;
    if ( mq->next == NULL )
    {
        aux = mq;
        rezultat = aux->nod;
        delete aux;
        mq = NULL;

    }
    else
    {
        aux = mq;
        rezultat = aux->nod;
        mq = mq->next;
        mq->prev = NULL;
        delete aux;
    }

    return rezultat;
}