#include <stdio.h>
#include <stdlib.h>

typedef struct list cell;

typedef struct list
{
    int data;
    cell *next;
} list;

int main ()
{
    FILE *in=fopen ("bfs.in","r");
    FILE *out=fopen ("bfs.out","w");
    int i,n,m,s,x,y,c[100000],d[100000];
    fscanf (in,"%d%d%d",&n,&m,&s);
    list **a=(list**) malloc (n*sizeof (list*));
    list **b=(list**) malloc (n*sizeof (list*)),*e;
    for (i=0; i<n; i++)
    {
        a[i]=NULL;
        c[i]=-1;
    }
    for (i=0; i<m; i++)
    {
        fscanf (in,"%d%d",&x,&y);
        x--; y--;
        if (!a[x])
        {
            a[x]=(list*) malloc (sizeof (list*));
            a[x]->data=y;
            a[x]->next=NULL;
            b[x]=a[x];
        }
        else
        {
            a[x]->next=(list*) malloc (sizeof (list*));
            a[x]=a[x]->next;
            a[x]->data=y;
            a[x]->next=NULL;
        }
    }
    c[s-1]=0;
    d[0]=s-1;
    x=0; y=1;
    while (x<y)
    {
        if (c[d[x]]!=-1)
        {
            e=b[d[x]];
            while (e)
            {
                if (c[e->data]==-1)
                {
                    d[y]=e->data;
                    c[e->data]=c[d[x]]+1;
                    y++;
                }
                e=e->next;
            }
        }
        x++;
    }
    for (i=0; i<n-1; i++) fprintf (out,"%d ",c[i]);
    fprintf (out,"%d\n",c[n-1]);
    fclose (in); fclose (out);
    return 0;
}