#include <iostream>
#include <cstdio>

using namespace std;

struct nod
{
    int inf;
    nod*a;
}*p[100010];

int n,m,s,a[100010];

void par(int k)
{
    for(nod*c=p[k];c!=NULL;c=c->a)
        if(a[c->inf]==-1 || a[c->inf]>a[k]+1)
    {
        a[c->inf]=a[k]+1;
        par(c->inf);
    }
}

int main()
{
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);
    scanf("%d %d %d",&n,&m,&s);
    int x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&x,&y);
        nod*c=new nod;
        c->inf=y;
        c->a=p[x];
        p[x]=c;
    }

    for(int i=1;i<=n;i++)
        a[i]=-1;
    a[s]=0;
    par(s);

    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    return 0;
}