#include <fstream>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

int N, M, start;
vector < vector <int> > graph;
vector <int> visited;

void BFS(int vertex) {
    if (vertex < 0 || vertex > N - 1) {
        return;
    }

    queue <int> Q;
    int node;
    Q.push(vertex);
    visited[vertex] = 0;

    while (!Q.empty()) {
        node = Q.front();
        for (int i = 0; i < graph[node].size(); ++i) {
            if (visited[graph[node][i]] == -1) {
                visited[graph[node][i]] = visited[node] + 1;
                Q.push(graph[node][i]);
            }
        }
        Q.pop();
    }
}

int main() {
    fin >> N >> M >> start;
    start--;
    graph.resize(N);
    visited.resize(N, -1);
    for (int i = 0; i < M; ++i) {
        int x, y;
        fin >> x >> y;
        x--;
        y--;
        graph[x].push_back(y);
    }

    BFS(start);

    for (int i = 0; i < N; ++i) {
        fout << visited[i] << ' ';
    }

    return 0;
}