#include <cstdio>
#include <algorithm>
#include <queue>

#define FIN "bfs.in"
#define FOUT "bfs.out"

#define N 100004

using namespace std;

vector <int> v[N];

queue <int> q;

int n, m, d[N], s;

void read()
{
    int x, y, i;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d%d%d", &n, &m, &s);

    for (i = 1; i <= m; ++i)
    {
        scanf("%d%d", &x, &y);

        v[x].push_back(y);
    }

    for (i = 1; i <= n; ++i)
        d[i] = -1;
}

void solve()
{
    int i, n1;

    q.push(s);

    d[s] = 0;

    while (!q.empty())
    {
        n1 = q.front();
        q.pop();

        for (i = 0; i < v[n1].size(); ++i)
            if (d[v[n1][i]] == -1)
            {
                d[v[n1][i]] = d[n1] + 1;
                q.push(v[n1][i]);
            }
    }
}

int main()
{
    int i;

    read();

    solve();

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

    printf("%d\n", d[n]);
}