using namespace std;
#include <fstream>
#include <stdlib.h>

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

int n,s;
int *G[100001];
int Q[100001];
int d[100001];
int viz[100001];


void read();
void solve();
void write();

int main ()
{
  read();
  solve();
  write();

}

void read()
{
   int i,j,m,x,y;
   f>>n>>m>>s;
   for(i=1; i<=n; i++)
   {
       G[i]=(int*)realloc(G[i],sizeof(int));
       G[i][0]=0;
   }
   for(i=1; i<=m; i++)
   {
       f>>x>>y;
       G[x][0]++;
       G[x]=(int*)realloc(G[x],(G[x][0]+1)*sizeof(int));
       G[x][G[x][0]]=y;
   }

}
void solve()
{
   int p,u,i,x;
   p=u=0;
   Q[0]=s;
   d[s]=0;
   viz[s]=1;
   while(p<=u)
   {
       x=Q[p++];
       for(i=1; i<=G[x][0]; i++)
          if(!viz[G[x][i]])
           {
               d[G[x][i]]=d[x]+1;
               Q[++u]=G[x][i];
               viz[G[x][i]]=1;
           }

   }
}

void write()
{
    int i;
    for(i=1; i<=n; i++)
    {
        if(!viz[i]) d[i]=-1;
        g<<d[i]<<" ";
    }
}