#include <iostream>
#include <stdio.h>

using namespace std;

int m,n,s,x[1000100],y[1000100],v[100100],i,j,k,d[1000100],a,b,u,p;


int main()
{

    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[i],&y[i]);
    }

    for (i=1;i<=n;i++)
    v[i]=-1;

    v[s]=0;

    p=0;u=1;d[1]=s;
    while (p<=u)
    {
        p++;

        for (i=1;i<=m;i++)
        {
            if (d[p]==x[i] and v[y[i]]==-1)
            {
                u++;
                d[u]=y[i];
                v[y[i]]=v[d[p]]+1;
            }
        }

    }


    for (i=1;i<=n;i++)
    printf("%d ",v[i]);


    return 0;
}