#include <stdio.h>
#include <queue>
#include <climits>
using namespace std;
FILE *f,*g;
int start[100010],t[1][1000010];
short int viz[100010];
queue<int> coada;
int drum[100010];
void FA_VECTOR(int n)
{
    int i;
    for(i=1;i<=n;i++)
        drum[i]=INT_MAX;
}
void BFS(int s)
{
    coada.push(s);
    int nod,vec,mm,drm;
    drum[s]=0;
    while(!coada.empty())
    {
        nod=coada.front();
        coada.pop();
        mm=start[nod];
        drm=drum[nod];
        viz[nod]=1;
        while(mm)
        {
            if(drm+1<drum[t[0][mm]]||!viz[t[0][mm]])
                coada.push(t[0][mm]),drum[t[0][mm]]=drum[nod]+1,viz[t[0][mm]]=1;
            mm=t[1][mm];
        }
    }
}
void Afisare(int n)
{
    int i;
    for(i=1;i<=n;i++)
        if(drum[i]==INT_MAX)
            fprintf(g,"-1 ");
        else
            fprintf(g,"%d ",drum[i]);

}
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]);*/
    FA_VECTOR(n);
    BFS(s);
    Afisare(n);
    fclose(f),fclose(g);
    return 0;
}