#include<fstream>
#define Nmax 1000001
#define infinit 1000001

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

int n,s,nr[Nmax],coada[Nmax];

struct nod
  {int info; // valoarea nodului respectiv
   nod *urm; //adresa urmatorului nod din lista
  };
nod *l[Nmax];

void citire()
{int i,m,x,y;
fin>>n>>m>>s;
for(i=1;i<=m;i++)
  {fin>>x>>y;
   nod *c;
   c=new nod;
   c->info=y;
   c->urm=l[x];
   l[x]=c;
  }
for(i=1;i<=n;i++)
  nr[i]=infinit;
}

void bfs()
{int x,p,u;
nod *c;
p=1;
coada[p]=s;
nr[s]=0;
u=1;
while(p<=u)
  {x=coada[p];
  p++;
  for(c=l[x];c!=NULL;c=c->urm)
    if(nr[c->info]>nr[x]+1)
      {u++;
      nr[c->info]=nr[x]+1;
      u++;
      coada[u]=c->info;
      }
  }
}


int main()
{citire();
bfs();
for(int i=1;i<=n;i++)
 if(nr[i]!=infinit) fout<<nr[i]<<" ";
   else fout<<"-1 ";
fin.close();
fout.close();
return 0;
}