#include <stdio.h>
#include <vector>

#define nmax 100001

using namespace std;

int N, M, Start, l;
vector<int> A[nmax];
int G[nmax], S[nmax], Solutie[nmax];

void BFS(int nodCurent)
{
    l = 1;
    Solutie[nodCurent] = 0;
    S[l] = nodCurent;

    for(int i = 1; i <= l; i++)
        for(int j = 0; j < G[S[i]]; j++)
            if(Solutie[A[S[i]][j]] == -1)
            {
                S[++l] = A[S[i]][j];
                Solutie[S[l]] = Solutie[S[i]] + 1;
            }
}

int main()
{
    freopen("bfs.in", "r", stdin);
    freopen("bfs.out", "w", stdout);

    int i, x, y;

    scanf("%d %d %d", &N, &M, &Start);

    for(int i = 1; i <= M; ++i) {
        scanf("%d %d", &x, &y);
        A[x].push_back(y); }

    for(int i = 1; i <= N; ++i)
        G[i] = A[i].size();

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

    BFS(Start);

    for(int i = 1; i <= N; ++i)
        printf("%d ", Solutie[i]);
    printf("\n");

    return 0;
}