#include <iostream>
#include <fstream>

struct nod
{
    int nd;
    nod * next;
};

nod * V[100001];
int viz[100001];
int s,n,m,prim,ultim,C[100001],Cost[100001];

using namespace std;

void bfs()
{
    int nr;
    nod * p;
    while (prim <= ultim)
    {
        p = V[C[prim]];
        while (p)
        {
            nr = p->nd;
            if (viz[nr]==0)
            {
                ultim++;
                C[ultim] = nr;
                viz[nr] = 1;
                Cost[nr] = prim;
            }
            p=p->next;
        }
        prim++;
    }
}

void afisare()
{
    ofstream g ("bfs.out");
    for(int i=1; i<=n; i++)
    {
            g<<Cost[i]<<" ";
    }
    g.close();
}

int main()
{
    ifstream f ("bfs.in");
    int i,j;
    nod * p;

    f>>n>>m>>s;

    for(int k=1; k<=m; k++)
    {
        f>>i>>j;
        p = new nod;
        p->nd = j;
        p->next = V[i];
        V[i] = p;
    }

    for(int i = 1; i<=n; i++)
    {
        viz[i] = 0;
        Cost[i] = -1;
    }

    prim = ultim = 1;
    C[prim] = s;
    viz[s] = 1;
    Cost[s] = 0;

    bfs();
    afisare();
}