#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int INF = 0x3f3f3f3f;

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

int N, M, start;
int D[MAXN];
vector <int> G[MAXN];
queue <int> Q;

void BFS()
{
    Q.push(start);
    for (int i = 1; i <= N; ++i)
        D[i] = INF;
    D[start] = 0;
    while (!Q.empty())
    {
        int node = Q.front(); Q.pop();
        for (vector <int> :: iterator it = G[node].begin(); it != G[node].end(); ++it)
        {
            int vecin = *it;
            if (D[vecin] > D[node] + 1)
            {
                D[vecin] = D[node] + 1;
                Q.push(vecin);
            }
        }
    }
    for (int i = 1; i <= N; ++i)
    {
        if (D[i] != INF) fout << D[i] << " ";
        else fout << "-1 ";
    }
}

int main()
{
    fin >> N >> M >> start;
    for (int a, b; M; --M)
    {
        fin >> a >> b;
        G[a].push_back(b);
    }
    BFS();
    fin.close();
    fout.close();
    return 0;
}