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

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

vector <vector<int>> adjacentList(100001);
vector <int> minDistance(1000001, -1);
queue <int> nextNodes;
int n, m, s, visited[100001];

void bfs(int node) {
    nextNodes.pop();
    for (int i = 0; i < adjacentList[node].size(); ++i) {
        int adjacentNode = adjacentList[node][i];
        if (!visited[adjacentNode]) {
            visited[adjacentNode] = 1;
            minDistance[adjacentNode] = minDistance[node] + 1;
            nextNodes.push(adjacentNode);
        }
    }
}


int main() {
    f >> n >> m >> s;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        f >> x >> y;
        adjacentList[x].push_back(y);
    }
    visited[s] = 1;
    minDistance[s] = 0;
    nextNodes.push(s);
    while (!nextNodes.empty()) {
        bfs(nextNodes.front());
    }
    for (int i = 1; i <= n; ++i) {
        g << minDistance[i] << " ";
    }
    return 0;
}