#include <fstream>
#include <vector>
#define Max 100010

using namespace std;

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

vector <int> V[Max];

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


void citire()
{
     int x,y;
     fin>>n>>m>>s;
     for (int i=0;i<m;i++)
     {
          fin>>x>>y;
          V[x].push_back(y);
     }
}

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 (typeof V[coada[i]].begin() j=V[coada[i]].begin();j<V[coada[i]].end();j++)
               if (rez[*j]==-1)
               {
                    rez[*j]=rez[coada[i]]+1;
                    coada[nr++]=*j;
               }
     }
}

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

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