#include <stdio.h>

int n, m, s, viz[1000005],coada[1000005],v[1000001];;

struct nod
{
    int info;
    nod *next;
};
nod *L[1000001];

void add(int x, int y)
{
    nod *p = new nod;
    p->info=y;
    p->next=L[x];
    L[x]=p;
}
void citire()
{
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);
    int x,y;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1; i<=m; ++i)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
    }
}
int main()
{
    int st,dr;
    citire();
    st=dr=1;
    coada[1]=s;
    for(int i=1; i<=n; ++i)
        v[i]=-1;
    v[s]=0;
    viz[s]=1;
    while ( st <= dr )
    {
        for ( nod *p = L[coada[st]]; p; p=p->next)
            if ( !viz[p->info] )
            {
                ++dr;
                coada[dr] = p->info;
                viz[p->info] = 1;
                v[p->info] = v[coada[st]] + 1;
            }
    st++;
    }
    for (int i = 1; i <= n; ++i)
        printf("%d ",v[i]);
	return 0;
}