#include <stdio.h>
#include <string.h>

#define Nmax 100100

int v[Nmax], w[Nmax],n,m,s;

struct Nod {int a; Nod *x;};

Nod *l[Nmax];



int main()
{
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);
    
    scanf("%d%d%d", &n,&m,&s);
    
    for (int i=1;i<=m;++i)
    {
        int a,b;
        Nod *q=new Nod;    
        scanf("%d%d", &a,&b);
        q->a = b;
        q->x = l[a];
        l[a] = q;        
    }
    
    memset(v,-1,sizeof(v));
    
    v[s] = 0;
    int st=0,dr=1;
    w[1] = s;
    while (st<dr)
    {
        int nod = w[++st];
        for (Nod *it=l[nod];it;it=it->x)
        if (v[it->a] == -1)
        {
            v[it->a] = v[nod] + 1;
            w[++dr] = it->a;    
        }    
    }
    
    for (int i=1;i<=n;++i) printf("%d ", v[i]);
    printf("\n");
    
    
    return 0;    
}