#include <fstream>
#define Max 100010

using namespace std;

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

struct nod
{
     int inf;
     nod * next;
}*sir[Max];

int n,m,s;
int rez[Max],coada[Max],nr;

void baga(int s,int d)
{
     nod *q=new nod;
     q->inf=s;
     q->next=sir[d];
     sir[d]=q;
}

void citire()
{
     int x,y;
     fin>>n>>m>>s;
     for (int i=0;i<m;i++)
     {
          fin>>x>>y;
          baga(y,x);
     }
}

void bfs()
{
     for (int i=0;i<=n;i++)
          rez[i]=-1;
     coada[nr++]=s;
     rez[s]=0;

     for (int i=0;i<nr;i++)
     {
          for (nod *j=sir[coada[i]];j;j=j->next)
               if (rez[j->inf]==-1)
               {
                    rez[j->inf]=rez[coada[i]]+1;
                    coada[nr++]=j->inf;
               }
     }
}

void afisare()
{
     for (int i=1;i<=n;i++)
          fout<<rez[i]<<" ";
}

int main ()
{
     citire();
     bfs();
     afisare();
     return 0;
}