#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

struct lista;

struct elem
{
    int info;
    elem *urm;
    elem()
    {
        info=-1;
        urm=NULL;
    }
    ~elem()
    {
        if(urm!=NULL)
            delete urm;
    }
    friend lista;
};

struct lista
{
    elem *urm,*u;
    lista()
    {
        urm=NULL;
        u=NULL;
    }
    ~lista()
    {
        if(urm!=NULL)
            delete urm;
    }
};

void bfs(lista *l[100001],int n,int x)
{
    int d[100001],i;
    memset(d,-1,sizeof(d));
    lista coada;
    d[x]=0;
    elem *p;
    p=new elem;
    p->info=x;
    coada.urm=p;
    coada.u=p;
    while(coada.urm!=NULL)
    {
        int y=coada.urm->info;
        elem *temp;
        temp=coada.urm;
        coada.urm=coada.urm->urm;
        temp->urm=NULL;
        delete temp;
        if(temp==coada.u)
            coada.u=NULL;
        elem *pi;
        for(pi=l[y]->urm;pi!=NULL;pi=pi->urm)
        {
            int z=pi->info;
            if(d[z]==-1)
            {
                elem *q;
                d[z]=d[y]+1;
                q=new elem;
                q->info=pi->info;
                if(coada.urm==NULL)
                {
                    coada.urm=q;
                    coada.u=q;
                }
                else
                {
                    coada.u->urm=q;
                    coada.u=q;
                }
            }
        }
    }
    ofstream g("bfs.out");
    for(i=1;i<=n;i++)
        g<<d[i]<<" ";
    g.close();
}

int main()
{
    int n,m,s,i;
    lista *l[100001];
    ifstream f("bfs.in");
    f>>n>>m>>s;
    for(i=1;i<=n;i++)
        l[i]=new lista;
    for(i=0;i<m;i++)
    {
        int x,y;
        f>>x>>y;
        elem *p;
        p=new elem;
        p->info=y;
        if(l[x]->u==NULL)
        {
            l[x]->urm=p;
            l[x]->u=p;
        }
        else
        {
            l[x]->u->urm=p;
            l[x]->u=p;
        }
    }
    f.close();
    bfs(l,n,s);
    for(i=1;i<=n;i++)
        delete l[i];
    return 0;
}