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

using namespace std;

vector<int> bfs(vector<vector<int>>& g, int s) {
    vector<int> vis(g.size(), 0);
    queue<pair<int, int>> q;
    vector<int> costs(g.size(), -1);
    q.push({s, 0});
    vis[s] = 1;
    costs[s] = 0;

    while (!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();

        int node = p.first, cost = p.second;
        
        for (int i = 0; i < (int)g[node].size(); i++) {
            if (vis[g[node][i]] == 0) {
                q.push({g[node][i], cost + 1});
                vis[g[node][i]] = 1;
                costs[g[node][i]] = cost + 1;
            }
        }
    }

    return costs;
    
}

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

    int n, m, s;
    fin >> n >> m >> s;
    
    vector<vector<int>> g(n+1);

    for (int i = 0; i < m; i++) {
        int x, y;
        fin >> x >> y;
        g[x].push_back(y);
    }

    vector<int> costs = bfs(g, s);
    for (unsigned int i = 1; i < costs.size(); i++) {
        fout << costs[i] << " ";
    }
    
    fout.close();
    return 0;
}