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

using namespace std;

using ListaVecini = vector<int>;
using Graf = vector<ListaVecini>;

vector<int> distanteBFS(const Graf& graf, int start) {
    vector<int> distante(graf.size(), -1);

    queue<int> coada;
    coada.push(start);
    distante[start] = 0;

    while (!coada.empty()) {
        int nod = coada.front();
        coada.pop();

        for (int i = 0; i < (int)graf[nod].size(); ++i) {
            int vecin = graf[nod][i];

            if (distante[vecin] == -1) {
                distante[vecin] = distante[nod] + 1;
                coada.push(vecin);
            }
        }
    }

    return distante;
}

int main() {
    ifstream in{ "bfs.in" };
    int n, m, s;
    in >> n >> m >> s;

    Graf graf(n + 1);

    for (int i = 1; i <= m; ++i) {
        int start, end;
        in >> start >> end;

        graf[start].push_back(end);
	}

	auto distante = distanteBFS(graf, s);

    ofstream out{ "bfs.out" };
    for (int nod = 1; nod <= n; ++nod) {
        out << distante[nod] << ' ';
    }
    out << '\n';
}