#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
using namespace std;

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

int main()
{
    int n, m, start;
    in >> n >> m >> start;
    start--;

    vector<vector<int>> vecin(n);

    for (int muchie = 0; muchie < m; muchie++) {
        int x, y;
        in >> x >> y;
        x--; y--;

        vecin[x].push_back(y);
    }

    vector<int> dist(n, -1);
    vector<bool> viz(n, false);
    dist[start] = 0;
    viz[start] = true;

    //BFS
    queue<int> Q;
    Q.push(start);

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

        for (int v : vecin[node]) {
            if (!viz[v]) {
                dist[v] = dist[node] + 1;
                viz[v] = true;

                Q.push(v);
            }
        }
    }
    //END

    for (int d : dist) {
        out << d << " ";
    }

    return 0;
}