#include <iostream>

using namespace std;

struct nod
{
    int info;
    nod *urm;
};

int n,m,p;
nod *a[100001];
int viz[100001];
int c[100001], pr, ul;
int lg[100001];

void AddLast(nod * & prim , int x)
{
  // creăm nod nou
  nod * q = new nod;
  q -> info = x;
  q -> urm = NULL;
  // adăugă noul nod la listă
  if(prim == NULL)
  { // lista este vidă
    prim = q;
  }
  else
  { // lista nu este vidă
    nod * t = prim;
    while(t -> urm != NULL)
      t = t -> urm;
    t -> urm = q;
  }
}

void CitireGraf()
{
    cin>>n>>m>>p;
    int x, y, i;
    for(i=1;i<=m;i++)
    {
        cin>>x>>y;
        AddLast(a[x], y);
    }
}

void BFS(int x)
{
    int v; nod *p;
    //cout<<x<<" ";
    viz[x]=1;
    c[1]=x; pr=ul=1;

    for(int i=1;i<=n;i++)
        lg[i]=-1;

    lg[x]=0;

    while(pr <= ul)
    {
        v=c[pr];
        for(p=a[v]; p!=NULL; p=p->urm)
            if(viz[p->info]==0)
            {
                viz[p->info]=1;
                //cout<<p->info<<" ";
                ul++;
                c[ul]=p->info;
                lg[p->info]=lg[v]+1;
            }
        pr++;
    }
}

int main()
{
    int i;

    CitireGraf();
    BFS(p);

    cout<<endl;
    for(i=1;i<=n;i++)
        cout<<lg[i]<<" ";

    return 0;
}