#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 100000;

vector <int> G[NMAX + 5];

queue <int> Q;

bool viz[NMAX + 5];

int dist[NMAX + 5], N, M, s;

void Read()
{
    int x, y;

    fin >> N >> M >> s;

    for(int i = 1; i <= M; i++) {
        fin >> x >> y;
        G[x].push_back(y);
    }
}

void BFS()
{
    Q.push(s);

    viz[s] = true, dist[s] = 1;

    while(!Q.empty()) {
        int node = Q.front();

        for(int i = 0; i < G[node].size(); i++) {
            int vecin = G[node][i];

            if(!viz[vecin]) {
                dist[vecin] = dist[node] + 1;
                viz[vecin] = true;
                Q.push(vecin);
            }
        }
        Q.pop();
    }
}

int main()
{
    Read();
    BFS();

    for(int i = 1; i <= N; i++)
        fout << dist[i] - 1 << " ";

    fout << '\n';

    fin.close();
    fout.close();

    return 0;
}