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

using namespace std;

struct Node
{
    int cost = -1;
    vector<int> edges;
};

using Graph = vector<Node>;

void Bfs(Graph &g, int start)
{
    queue<int> q;
    vector<bool> in_queue(g.size(), false);

    q.push(start);
    g[start].cost = 0;

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

        in_queue[node] = false;

        for (int next : g[node].edges) {
            if (g[next].cost == -1 || g[next].cost > g[node].cost + 1) {
                g[next].cost = g[node].cost + 1;
                if (!in_queue[next]) {
                    q.push(next);
                    in_queue[next] = true;
                }
            }
        }
    }
}

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

    int n, m, s;
    fin >> n >> m >> s;

    Graph graph(n);
    while (m--) {
        int x, y;
        fin >> x >> y;
        graph[x - 1].edges.push_back(y - 1);
    }

    Bfs(graph, s - 1);
    for (const auto &node : graph) {
        fout << node.cost << " ";
    }
    fout << "\n";

    return 0;
}