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

using namespace std;

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

const int dim = 100001;
vector<int>graph[dim];
const int infinity = 10000000;
int d[dim], s, nodes, edges;
bool check[dim];

void input() {
    in >> nodes >> edges >> s;
    for (int i = 1; i <= edges; i++) {
        int u, v;
        in >> u >> v;
        graph[u].push_back(v);
    }
}

queue<int>q;

void bfs(int s) {
    for (int i = 1; i <= nodes; i++) {
        d[i] = infinity;
    }

    d[s] = 0;
    check[s] = true;
    q.push(s);

    while (q.empty() == false) {
        int node = q.front();
        q.pop();
        for (size_t j = 0; j < graph[node].size(); j++) {
            int vecin = graph[node][j];
            if (!check[vecin]) {
                check[vecin] = true;
                q.push(vecin);
                d[vecin] = 1 + d[node];
            }
        }
    }
}

int main() {

    input();
    bfs(s);

    for (int i = 1; i <= nodes; i++) {
        if (d[i] == infinity) {
            out << "-1 ";
        } else {
        out << d[i] << " ";
        }
    }
	return 0;
}