#pragma region
#include <bits/stdc++.h>
using namespace std;
// File
ifstream fin("bfs.in");
ofstream fout("bfs.out");
#pragma endregion

void BFS(vector<vector<int>> adj, vector<int>& vis, int start) {
    queue<int> node;    node.push(start);
    vis[start] = 0;

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

        for (int i = 0; i < int(adj[currNode].size()); i++)
            if (vis[adj[currNode][i]] == -1) {
                node.push(adj[currNode][i]);
                vis[adj[currNode][i]] = vis[currNode] + 1;
            }
    }
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

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

    vector<vector<int>> adj(n);
    vector<int> vis(adj.size(), -1);
    for (int i = 0; i < m; i++) {
        int x, y;
        fin >> x >> y;
        adj[--x].push_back(--y);
    }

    BFS(adj, vis, s);

    for (int i = 0; i < n; i++)
        fout << vis[i] << ' ';


    return 0;
}