#include <fstream>
#define Max 100005

using namespace std;

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

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

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

void inserare(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;
          inserare(y,x);
     }
}

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

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

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

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