#include<fstream.h>
#define N 100001
typedef struct nod
{long val;
struct nod *leg;}Nod;
typedef struct
{Nod *prim,*ultim;}coada;

void add(long x,coada &q)
{Nod *px=new Nod;
px->val=x;
px->leg=NULL;
if(q.prim==NULL)
      q.prim=q.ultim=px;
else
      {q.ultim->leg=px;
      q.ultim=px;}}

long del(coada &q)
{Nod *t=q.prim->leg;
long x=q.prim->val;
free(q.prim);
q.prim=t;
if(q.prim==NULL)
      q.ultim=NULL;
return x;}

int main()
{long n,m,s,k,i,j,d[N],c[N]={0};
coada q,l[N];
q.prim=q.ultim=NULL;
ifstream f("bfs.in");
ofstream h("bfs.out");
f>>n>>m>>s;
for(i=1;i<=n;i++)
     {d[i]=N;
     l[i].prim=l[i].ultim=NULL;}
for(k=1;k<=m;k++)
     {f>>i>>j;
     add(j,l[i]);}
c[s]=1,d[s]=0;
add(s,q);
while(q.prim!=NULL)
     {i=del(q);
     while(l[i].prim!=NULL)
            {j=del(l[i]);
            if(!c[j])
                     {d[j]=d[i]+1,c[j]=1;
                     add(j,q);}}}
for(i=1;i<=n;i++)
if(d[i]==N)
     h<<"-1 ";
else
     h<<d[i]<<" ";
f.close();
h.close();
return 0;}