#include <deque>
#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);
    vector<bool> vizitat(graf.size());

    deque<int> coada;
    coada.push_back(start);
    distante[start] = 0;

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

        vizitat[nod] = true;

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

            if (!vizitat[vecin]) {
                distante[vecin] = distante[nod] + 1;
                coada.push_back(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';
}