///Fiind dat un nod S, sa se determine, pentru fiecare nod X,
///numarul minim de arce ce trebuie parcurse pentru a ajunge
///din nodul sursa S la nodul X.
#include <stdio.h>
#include <queue>
using namespace std;
FILE *f,*g;
int start[100010],t[1][1000010];
queue<int> coada;
int drum[100010];
void BFS(int s)
{
    coada.push(s);
    int nod,vec,mm;
    drum[s]=1;
    while(!coada.empty())
    {
        nod=coada.front();
        coada.pop();
        mm=start[nod];
        while(mm)
        {
            if(!drum[t[0][mm]])
                coada.push(t[0][mm]),drum[t[0][mm]]=drum[nod]+1;
            mm=t[1][mm];
        }
    }
}
void Afisare(int n)
{
    int i;
    for(i=1;i<=n;i++)
        fprintf(g,"%d ",drum[i]-1);
}
int main()
{
    f=fopen("bfs.in","r");g=fopen("bfs.out","w");
    int n,m,i,s,x,y,k=0;
    fscanf(f,"%d %d %d\n",&n,&m,&s);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d %d",&x,&y);
        t[0][i]=y;
        t[1][i]=start[x];
        start[x]=i;
    }
    fprintf(g,"START ={ ");
  /*  for(i=1;i<n;i++)
        fprintf(g,"%d,",start[i]);
    fprintf(g,"%d }\n",start[n]);
    fprintf(g,"T[0]  ={ ");
    for(i=1;i<m;i++)
        fprintf(g,"%d,",t[0][i]);
    fprintf(g,"%d }\n",t[0][m]);
    fprintf(g,"T[1]  ={ ");
    for(i=1;i<m;i++)
        fprintf(g,"%d,",t[1][i]);
    fprintf(g,"%d }",t[1][i]);*/
    BFS(s);
    Afisare(n);
    fclose(f),fclose(g);
    return 0;
}