#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

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

int n,m,p;

nod *a[100001];
nod *prim, *ultim;

int viz[100001];
int c[100001], pr, ul;
int lg[100001];

void AddLast(nod* &prim, nod *& ultim, int x)
{
    nod *p;
    p = new nod;
    p->info = x;
    p->urm = NULL;
    if(prim == NULL)
        prim = ultim = p;
    else
    {
        ultim->urm=p;
        p=ultim;
    }
}

void CreareLista(nod *& prim, nod *& ultim)
{

}

void CitireGraf()
{
    fin>>n>>m>>p;
    int x, y, i;

    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        AddLast(a[x], a[x], y); /// n am nicio idee daca e asa
    }
}

void BFS(int x)
{
    int v; nod *p;
    viz[x]=1;
    c[1]=x; pr=ul=1;

    for(int i=1;i<=n;i++)
        lg[i]=-1;

    lg[x]=0;

    while(pr <= ul)
    {
        v=c[pr];
        for(p=a[v]; p!=NULL; p=p->urm)
            if(viz[p->info]==0)
            {
                viz[p->info]=1;
                ul++;
                c[ul]=p->info;
                lg[p->info]=lg[v]+1;
            }
        pr++;
    }
}

int main()
{
    int i;

    CitireGraf();
    BFS(p);

    for(i=1;i<=n;i++)
        fout<<lg[i]<<" ";

    return 0;
}