#include <cstdio>
struct nod{int nd; nod *next;};
nod *L[100100];
struct coada{int val;int d;};
coada C[100100], X;
int n, m, s, uz[100100];
void citire()
{
    nod *p;
    int i, x, y;
    scanf("%d%d%d", &n, &m, &s);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d", &x, &y);
        p=new nod;
        p->nd=y;
        p->next=L[x];
        L[x]=p;
    }
    for(i=1;i<=n;++i)
        uz[i]=-1;
}
void bfs()
{
    nod *p;
    int ic, sf;
    ic=sf=1;
    C[ic].val=s;
    C[ic].d=0;
    uz[s]=0;
    while(ic<=sf)
    {
        X=C[ic++];
        p=L[X.val];
        while(p)
        {
            if(uz[p->nd]==-1)
            {
                C[++sf].val=p->nd;
                C[sf].d=X.d+1;
                uz[p->nd]=X.d+1;
            }
            p=p->next;
        }
    }
}
void afisare()
{
    int i;
    for(i=1;i<=n;++i)
        printf("%d ", uz[i]);
}
void rezolva_problema()
{
    citire();
    bfs();
    afisare();
}
int main()
{
    freopen("bfs.in", "r", stdin);
    freopen("bfs.out", "w", stdout);
    rezolva_problema();
    return 0;
}