#include<stdio.h>
#include<queue.h>
#include<vector.h>
#define dim 100100
#define pb push_back

vector <int> v[dim];
queue <int> q;
int a[dim],n,m,nod;
//--------------------------------------------------------------------------
void afis()
{
     for(int i=1 ; i<=n;i++)
     printf("%d ",a[i]);
     printf("\n");
}
//--------------------------------------------------------------------------
void add(int x , int y)
{
     v[x].pb(y);
}
//--------------------------------------------------------------------------
void read()
{
     int x,y;
     scanf("%d %d %d\n",&n,&m,&nod);
     for(int i=1 ; i<=m;i++)
     {
             scanf("%d %d\n",&x,&y);
             add(x,y);
             }
}
//--------------------------------------------------------------------------
int vectorset87(int a[dim],int x,int n)
{
              for(int i=0 ; i<=n;i++)
              a[i]=x;
}
//--------------------------------------------------------------------------
void solve()
{
     int x,k;
     read();
     vectorset87(a,-1,n+1);
     a[nod]=0;
     for(q.push(nod) ; !q.empty() ; q.pop() )
     {
          x=q.front();
          for(int i=0 ; i<v[x].size() ; i++)
          {
            k = v[x][i];    
          //  printf("%d\n",k);
                  if (a[k]==-1 || (a[k]> a[x]+1))
                  {
                               q.push(k);
                               a[k] = a[x] + 1;
                               }
                  }           
                     }
     afis();

 }
//--------------------------------------------------------------------------
int main ()
{
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);
    solve();
    return 0;
}

//--------------------------------------------------------------------------