#include <fstream>
#define nmax 100001
using namespace std;

struct nod_lista{
    int vecin;
    nod_lista *link;
};

nod_lista *G[nmax];
int Q[nmax],D[nmax],Viz[nmax];
int N,M,S;

void adauga(int unde,int ce)
{
    nod_lista *q=new nod_lista;

    q->vecin=ce;
    q->link=G[unde];
    G[unde]=q;
}

void citeste()
{
    ifstream f("bfs.in");
    int i,x,y;

    f>>N>>M>>S;
    for(i=1;i<=M;i++)
    {
        f>>x>>y;
        adauga(x,y);
    }

    for(i=1;i<=N;i++)
    D[i]=-1;

    f.close();
}

void BFS(int S)
{
    nod_lista *it;
    int p,q,vecin;

    p=q=0;
    Q[++q]=S;
    Viz[S]=1;
    D[S]=0;

    while(p<=q)
    {
        int nod=Q[++p];
        it=G[nod];

        while(it)
        {
            if(!Viz[it->vecin])
            {
                Viz[it->vecin]=1;
                D[it->vecin]=D[nod]+1;
                Q[++q]=it->vecin;
            }
            it=it->link;
        }
    }
}

void rezolva()
{
    BFS(S);
}

void scrie()
{
    ofstream g("bfs.out");
    int i;

    for(i=1;i<=N;i++)
    g<<D[i]<<' ';

    g<<'\n';
    g.close();
}

int main()
{
    //cout << "Hello world!" << endl;
    citeste();
    rezolva();
    scrie();
    return 0;
}