#include <iostream>
#include<fstream>
#include<cstdlib>

using namespace std;
typedef struct nod
{
    int val;
    nod *urm;
}NOD;
typedef struct lista
{
    int nr_el;
    NOD *primVecin,*ultimVecin;
}LISTA;

int n,m,S;
LISTA *listaVecini[100001];
LISTA *BFS;
int viz[100001];
int d=0,D[100001];

void init(int k)
{
    for(int i=1;i<=k;i++)
        {
            listaVecini[i]=(LISTA*)malloc(sizeof(LISTA*));
            listaVecini[i]->nr_el=0;
            viz[i]=0;
            D[i]=-1;
        }
    BFS=(LISTA*)malloc(sizeof(LISTA*));
    BFS->nr_el=0;
}

int adaug_nod(int v,LISTA *l)
{
    NOD* c;
    c=(NOD*)malloc(sizeof(NOD*));
    if(!c) return 0;
    c->val=v;
    c->urm=0;
    if(!l->nr_el)
    {
        l->primVecin=l->ultimVecin=c;
    }
    else
    {
        l->ultimVecin->urm=c;
        l->ultimVecin=c;
    }
    l->nr_el++;
    return 1;
}

int sterg_nod(LISTA *l)
{
    NOD* c;
    int r;
    if(l->nr_el==0) return 0;
    else
    {
       c=l->primVecin;
       r=c->val;
       l->primVecin=c->urm;
       delete(c);
       l->nr_el--;
       return r;
    }
}


//Nu sterg nodurile vecine pe care le afisez, ci le marchez ca fiind vizitate
// Le voi sterge dupa ce le-am afisat si vecinii lor
void latime(int k0)
{
    int u;
   viz[k0]=1;
   D[k0]=0;
   adaug_nod(k0,BFS);
   while(BFS->nr_el)
   {
       NOD *c,*p;
        p=BFS->primVecin;  //p este primul din coada BFS

        c=listaVecini[p->val]->primVecin; //parcurg lista de vecini ai lui p, fara stergere
        while(c)
        {
            if(c->val!=k0 && !viz[c->val])
            {
                viz[c->val]=1;
                D[c->val]=D[p->val]+1;
                //cout<<c->val<<" ";
                adaug_nod(c->val,BFS);
            }
            c=c->urm;
        }
        u=sterg_nod(BFS); //sterg nodul pentru care am afisat vecinii
    }



    while(BFS->nr_el)  // apelez pentru vecini
        {
            latime(BFS->primVecin->val);
        }
}

void citire()
{
    int x,y;

    FILE* fin=fopen("bfs.in","rt");
    fscanf(fin,"%d %d %d",&n,&m,&S);
    init(n);
    for(int i=0;i<m;i++)
        {
            fscanf(fin,"%d %d",&x,&y);
            if(x!=y) adaug_nod(y,listaVecini[x]);
            //adaug_nod(x,listaVecini[y]); //numai pentru graf neorientat
        }
    fclose(fin);
}

void afisare_liste()
{
    for(int i=1;i<=n;i++)
        {
            int nr;
            cout<<i<<": ";
            while(nr=sterg_nod(listaVecini[i])) cout<<nr<<" ";
            cout<<"\n";
        }
}
int main()
{
    int nr;
    citire();
   // afisare_liste();

    latime(S);
   // cout<<"\n";
   FILE* fout=fopen("bfs.out","wt");
    for(int i=1;i<=n;i++)
        fprintf(fout,"%d ",D[i]);
    fclose(fout);
    return 0;
}