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

int distanta[1000000];
vector<int> varfuri[100001];

int main() {
    int N, M, S;
    ifstream fin ("bfs.in");
    ofstream fout ("bfs.out");
    fin >> N >> M >> S;
    int varfPlecare, varfDestinatie;
    while (M) {
        fin >> varfPlecare >> varfDestinatie;
        varfuri[varfPlecare].push_back(varfDestinatie);
        --M;
    }
    queue<int> coada;
    int cost = 0;
    coada.push(S);
    distanta[S] = 0;
    while (!coada.empty()) {
        int nod = coada.front();
        for (int i = 0; i < varfuri[nod].size(); ++i) {
            coada.push(varfuri[nod][i]);
            distanta[varfuri[nod][i]] = cost + 1;
        }
        ++cost;
        coada.pop();
    }
    for (int i = 1; i <= N; ++i)
        fout << distanta[i] << " ";
    fout.close();
    return 0;
}