/// Nr. arce (lungimea lantului de la start la X) inseamna ca lungimea pana la noul nod
/// vizitat e lungimea nodului curent + 1 (nodul de start incepe cu lungimea 0)

#include <fstream>
#include <vector>

#define NMAX 100009

std::vector<int> Adiacenta[NMAX];  // liste de adiacenta

int main()
{
    std::ifstream f("bfs.in");
    std::ofstream g("bfs.out");
    int N, M, S;
   
    f >> N >> M >> S;
    for (int x, y, i = 0; i < M; ++i)
    {
        f >> x >> y;
        Adiacenta[x].push_back(y);
    }

    int nrArce[NMAX];
    int coada[NMAX], st = 1, dr = 1;

    for (int i = 1; i <= N; ++i)
        nrArce[i] = -1;
    nrArce[S] = 0;
    coada[st] = S;
    while (st <= dr)
    {
        int curent = coada[st++];
        for (auto it = Adiacenta[curent].begin(); it != Adiacenta[curent].end(); ++it)
            if(nrArce[*it] == -1)
            {
                coada[++dr] = *it;
                nrArce[*it] = nrArce[curent] + 1;
            }
    }

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

    return 0;
}