#include <stdio.h>

struct muchie{
    int i;
    int j;
};

int n,m,nv[100005],lv[1000005],d[100005],q[100005],nq,cq;
muchie mx[1000005];


int vecin(int i,int k)
{
    if(mx[k].i==i)
        return mx[k].j;
    return mx[k].i;
}


int main()
{
    int i,j,k,s;
    FILE *f,*g;

    f=fopen("bfs.in","r");
    g=fopen("bfs.out","w");

    fscanf(f,"%d%d%d",&n,&m,&s);


    for (k=1;k<=m;k++)
    {
        fscanf(f,"%d%d",&i,&j);
        nv[i]++;
        mx[k].i=i;mx[k].j=j;
    }
    for(i=2;i<=n;i++)
        nv[i]+=nv[i-1];
    for(k=1;k<=m;k++)
    {
        i=mx[k].i;
        lv[nv[i]--]=k;
    }
    nv[n+1]=m;
    for(i=1;i<=n;i++)
        d[i]=-1;
    d[s]=0;
    cq=0;nq=1;q[1]=s;
    while(cq<nq)
    {
        cq++;i=q[cq];
        for(k=nv[i]+1;k<=nv[i+1];k++)
        {
            j=vecin(i,lv[k]);
            if(d[j]<0)
            {
                d[j]=d[i]+1;
                nq++;q[nq]=j;
            }
        }
    }
    for(i=1;i<=n;i++)
        fprintf(g,"%d ",d[i]);

}