#include <cstdio>
#include <queue>
using namespace std;
int n,i,m,x,y,u[100000],s,v[100000],nr;
queue <int> q;
struct l
{
    int nod;
    l *urm;
} *g[100000];
void lista(int x, int y)
{
    l *p;
    p=new l;
    p->nod=y;
    p->urm=g[x];
    g[x]=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,&y);
        lista(x,y);
    }

    /*for (i=1; i<=n; ++i)
    {
        while(g[i]!=NULL)
        {
            printf("%d ",g[i]->nod);
            g[i]=g[i]->urm;
        }
        printf("\n");
    }*/

    /*for (i=1; i<=n; ++i)
    {
        if (u[i]==0)
        {
            q.push(i);
            u[i]=1;
            while (!q.empty())
            {
                x=q.front();
                printf("%d ",x);
                while(g[x]!=NULL)
                {
                    if (u[g[x]->nod]==0)
                    {
                        q.push(g[x]->nod);
                        u[g[x]->nod]=1;
                    }
                    g[x]=g[x]->urm;

                }
                q.pop();

            }
        }
    }*/

    q.push(s);
    u[s]=1;

    while (!q.empty())
    {
        x=q.front();
        nr++;
        while(g[x]!=NULL)
        {
            if (u[g[x]->nod]==0)
            {
                q.push(g[x]->nod);
                u[g[x]->nod]=1;
                v[g[x]->nod]=nr;
            }
            g[x]=g[x]->urm;

        }
        q.pop();

    }
    for (i=1;i<=n;++i)
    {
        if (i==s) printf("0 ");
        else if (u[i]==0) printf("-1 ");
        else printf("%d ",v[i]);
    }
    return 0;
}