#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>

using namespace std;

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

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

coada *prim=NULL, *ultim=NULL;

vector <int> G[100005];

int N, M, S;
int d[100005];

void pop()
{
    coada *p=prim;
    prim=prim->urm;
    delete p;
}

void push(int info)
{
    if (prim==NULL)
    {
        prim = new coada;
        prim->info=info;
        prim->urm=NULL;
        ultim=prim;
    }
    else
    {
        coada *p = new coada;
        p->info=info;
        p->urm=NULL;
        ultim->urm=p;
        ultim=p;
    }
}

int cfront()
{
    return prim->info;
}

bool cempty()
{
    return prim!=NULL;
}

void citire()
{
    fin >> N >> M >> S;
    for (int i=1; i<=M; i++)
    {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
    }
}

void BFS(int start)
{
    memset(d, -1, sizeof(d));
    d[start]=0;

    push(start);

    while (cempty())
    {
        int nod=cfront();
        pop();
        for (int i=0; i<(int)G[nod].size(); i++)
        {
            int vecin=G[nod][i];
            if (d[vecin]==-1)
            {
                d[vecin]=d[nod]+1;
                push(vecin);
            }
        }
    }
}

void afisare()
{
    for (int i=1; i<=N; i++)
        fout << d[i] << " ";
}

int main()
{
    citire();
    BFS(S);
    afisare();
    return 0;
}