#include <cstdio>
#include <algorithm>
using namespace std;
struct aa{int x;int y;};
aa muchie[1000003];
int d[100002],c[100002],start[100002];
int cmp(aa u,aa v)
{
    return u.x<v.x;
}
int main()
{
    int n,i,j,s,m;
    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",&muchie[i].x,&muchie[i].y);
    sort(&muchie[1],&muchie[m+1],cmp);
    for(i=1;i<=m;i++)
        if(muchie[i].x!=muchie[i-1].x)
            start[muchie[i].x]=i;
    c[1]=s;
    d[s]=1;
    int p,u;
    p=u=1;
    while(p<=u)
    {
        j=c[p];
        p++;
        for(i=start[j];muchie[i].x==j&&i<=m;i++)
            if(d[muchie[i].y]==0)
                d[muchie[i].y]=d[j]+1,u++,c[u]=muchie[i].y;
    }
    for(i=1;i<=n;i++)
        printf("%d ",d[i]-1);
    return 0;
}