#include <cstdio>

using namespace std;
struct graf
{
    int x;
    graf *u;
};
graf *a[100001];
int c[100001],d[100001];
int ultim,nr,s;
void bag(int x,int y)
{
    graf *q=new graf;
    q->x=y;
    q->u=a[x];
    a[x]=q;
}
void par(int x)
{
    graf *q=a[x];
    while(q!=NULL)
    {
        if((d[q->x]==0)&&(q->x!=s))
        {
            ++ultim;
            c[ultim]=q->x;
        }
        q=q->u;
    }
}
int main()
{
    short e=0;
    int i,n,m,x,y;
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);
    scanf("%d%d%d",&n,&m,&s);
    for(i=0;i<m;++i)
    {
        scanf("%d%d",&x,&y);
        bag(x,y);
    }
    c[1]=s;
    x=1;
    y=1;
    ultim=1;
    while(e==0)
    {
        while(x<=y)
        {
        if (d[c[x]]==0) d[c[x]]=nr;
            par(c[x]);
            ++x;
        }
        if(y==ultim) e=1;
        else
        {
            y=ultim;
            ++nr;
        }
    }
    for(i=1;i<n;++i)
    if (d[i]==0)
    {
        if (i==s) printf("0 ");
        else printf("-1 ");
    }
    else printf("%d ",d[i]);
    if (d[n]==0)
    {
        if (n==s) printf("0\n");
        else printf("-1\n");
    }
    else printf("%d\n",d[n]);
    return 0;
}