#include <fstream>

using namespace std;

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

typedef nod *lda1;

lda1 lda[100005];

int n,m,s,x,y,coada[100005],parc[100005],nr,dist[100005];

int main()
{
    ifstream in ("bfs.in");
    ofstream out ("bfs.out");

    in>>n>>m>>s;

    for (int i=1;i<=m;++i)
    {
        in>>x>>y;
        lda1 p=new nod;
        p->urm=y;
        p->adr=lda[x];
        lda[x]=p;
    }

    for (int i=1;i<=n;++i) dist[i]=-1;
    nr=1; coada[1]=s; dist[s]=0; parc[s]=1;

    int init=1;
    while (init<=nr)
    {
        for (lda1 p=lda[coada[init]];p!=0;p=p->adr)
        {
            if (parc[p->urm]==0)
            {
                dist[p->urm]=dist[coada[init]]+1;
                parc[p->urm]=1;
                ++nr;
                coada[nr]=p->urm;
            }
        }
        ++init;
    }

    for (int i=1;i<=n;++i) out<<dist[i]<<" ";

    in.close();
    out.close();
    return 0;
}