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

using namespace std;

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


int main() {
    int n, m, s; // noduri, muchii, nodul de start
    int x, y, current;
    vector<vector<int>> l; //lista vecini

    fin >> n >> m >> s;

    l.resize(n + 1);

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

    vector<int> dist(n+1, -1), viz(n+1, 0);
    queue<int> coada;

    coada.push(s);
    dist[s] = 0;
    viz[s] = 1;
    while (coada.size() > 0) {
        current = coada.front();
        coada.pop();
        for (auto i: l[current]) {
            if (viz[i] == 0) {
                coada.push(i);
                viz[i] = 1;
                dist[i] = dist[current] + 1;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        fout << dist[i] << " ";
    }


  }