#include <cstdio>
#include <vector>
#include <memory.h>

using namespace std;

#define Nmax 10005

int N, M, S, LQ, G[Nmax], Q[Nmax], Cost[Nmax];
vector <int> A[Nmax];

void Citire()
{
    int n1, n2;
    scanf("%d%d%d", &N, &M, &S);
    for (int i = 1; i <= M; i++)
    {
        scanf("%d%d", &n1, &n2);
        A[n1].push_back(n2);
    }
    for (int i = 1; i <= N; i++)
        G[i] = A[i].size();
}

void BFS()
{
    memset(Cost, -1, sizeof(Cost));
    LQ = 1;
    Cost[S] = 0;
    Q[1] = S;
    for (int i = 1; i <= LQ; i++)
        for (int j = 0; j < G[Q[i]]; j++)
            if (Cost[A[Q[i]][j]] == -1)
            {
                Q[++LQ] = A[Q[i]][j];
                Cost[Q[LQ]] = Cost[Q[i]] + 1;
            }
}

void Afisare()
{

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

}

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

    Citire();
    BFS();
    Afisare();

    return 0;
}