#include <stdio.h>

using namespace std;

const int N=100001;
const int M=1000001;
const int NIL=-1;

struct nod
{
    int val;
    int urm;
};

nod a[2*M];
int q[N],list[N],d[N],nr=0,p,u,n,m,s;

int main()
{
    FILE *in,*out;
    in=fopen("bfs.in","r");
    out=fopen("bfs.out","w");
    int i,x,y,poz;
    fscanf(in,"%d%d%d",&n,&m,&s);
    for(i=1;i<=n;i++) {list[i]=NIL; d[i]=NIL;}
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d%d",&x,&y);
        a[nr].val=y;
        a[nr].urm=list[x];
        list[x]=nr++;
    }
    q[0]=s;
    d[s]=0;
    p=0; u=1;
    while(p!=u)
    {
        x=q[p];
        p=(p+1)%n;
        poz=list[x];
        while(poz!=NIL)
        {
            y=a[poz].val;
            if(d[y]==NIL)
            {
                q[u]=y;
                u=(u+1)%n;
                d[y]=1+d[x];
            }
            poz=a[poz].urm;
        }
    }
    for(i=1;i<=n;i++) fprintf(out,"%d ",d[i]);
    return 0;
}