#include <fstream>

using namespace std;

ifstream f("bfs.in");
ofstream g("bfs.out");

struct nod{
    int inf;
    nod *urm;
};

nod *v[1000001],*j;
int i,n,viz[1000001],m,s,x,y,Q[1000001],l,e,p;

void adaug(nod *&p, int x)
{
    nod *e,*u;
    e=new nod;
    e->inf = x;
    e->urm = NULL;
    if(p==NULL)
        p=e;
    else
    {
        u=p;
        while(u->urm!=NULL)
            u=u->urm;
            u->urm=e;
    }
}

int main()
{
    f>>n>>m>>s;
    for(i=1;i<=m;i++)
        {
            f>>x>>y;
            adaug(v[x],y);
        }

    Q[1]=s;
    p=1;
    l=1;
    viz[s]=1;
    while(p<=l)
    {
        e=Q[p];
        j=v[e];
        if(j==NULL)
            p++;
        else
        {
            while(j->urm!=NULL)
            {
                if(viz[j->inf]==0)
                {
                    l++;
                    Q[l]=j->inf;
                    viz[Q[l]]=viz[Q[p]]+1;
                }
                j=j->urm;
            }
            if(viz[j->inf]==0)
            {
                l++;
                Q[l]=j->inf;
                viz[Q[l]]=viz[Q[p]]+1;
            }
            p++;
        }
    }

    for(i=1;i<=n;i++)
        g<<viz[i]-1<<" ";

    return 0;
}