#include <stdio.h>
int n,m,s;
struct nod{int val; nod *next;};
nod *G[100001];
int i,q[100001],x,y,val[100001];
int add(int a, int b)
{
    nod *nou=new nod;
    nou->val=y;
    nou->next=G[x];
    G[x]=nou;
    return 0;
}
int main(void)
{
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);
    scanf("%d%d%d",&n,&m,&s);
    for (i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    for (i=1;i<=n;i++) val[i]=-1;
    val[s]=0;
    q[++q[0]]=s;
    int i=0;
    while (i<=q[0])
    {
        nod *nou=new nod;
        nou=G[q[i]];
        while (nou)
        {
            if (val[nou->val]==-1 || val[nou->val]>val[q[i]]+1) {val[nou->val]=val[q[i]]+1; q[++q[0]]=nou->val;}
            nou=nou->next;
        }
        i++;
    }
    for (i=1;i<=n;i++) printf("%d ",val[i]);
    return 0;
}