#include<iostream>
#include<fstream>

#define IMAX 100000

using namespace std;

struct que {
            int util;
            que *urm;
           }*p;


int n,i,j,m,S;
int *a[IMAX];
int culoare[IMAX],cost[IMAX];
//int drum[IMAX];

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

void citire()
{
    int x,y;
    f>>n>>m>>S;
    for(i=1;i<=n;i++)
        {
            a[i]=(int*)realloc(a[i],sizeof(int));
            a[i][0]=0;
            cost[i]=-1;
        }
    for(i=1;i<=m;i++)
        {
         f>>x>>y;
        a[x]=(int *)realloc(a[x],a[x][0]+sizeof(int));
        a[x][++a[x][0]]=y;
        }

}

void afis()
{
    for(i=1;i<=n;i++)
        {for(j=1;j<=a[i][0];j++)
            cout<<a[i][j]<<" ";
        cout<<"\n";}
}

que *q, *coada;
void insertie(int nr)
{

 if(coada==NULL)
    {
        coada=new que;
        p=new que;
        coada->util=nr;
        coada->urm=NULL;
        p=coada;
    }
  else
   {
       q=new que;
       q->util=nr;
       coada->urm=q;
       q->urm=NULL;
       coada=q;

   }
}

void scoate()
{
   que *O;
    O=new que;
    O=p;
    p=p->urm;
    delete O;
}

void parc_latime(int x)
{
 //0- alb
 //1- gri
 //2- negru
int d=0;


cost[x]=0;
 insertie(x);
 culoare[x]=1;
while(p!=NULL)
 {
   x=p->util;
 for(i=1;i<=a[x][0];i++)
        if(culoare[a[x][i]]==0)
            {
                insertie(a[x][i]);
                culoare[a[x][i]]=1;
               // drum[a[x][i]]=x;
                cost[a[x][i]]=cost[x]+1;

            }
    culoare[x]=2;

    scoate();

    }


}

int main()
{
citire();


parc_latime(S);
for(i=1;i<=n;i++)
    o<<cost[i]<<" ";




return 0;}