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

using namespace std;

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

const int N_MAX = 100000;

struct Nod {
    bool vizitat = false;
    int distanta = -1;
    vector<int> indexVecini;
};

int N, M, S;
Nod noduri[N_MAX];
queue<int> bfsQueue;

void citire() {
    fin >> N >> M >> S;
    int outNod, inNod;
    for (int i = 0; i < M; i++) {
        fin >> outNod >> inNod;
        noduri[outNod - 1].indexVecini.push_back(inNod - 1);
    }
}

void BFS() {
    while (!bfsQueue.empty()) {
        int parent = bfsQueue.front();
        bfsQueue.pop();
        for(int nodNou : noduri[parent].indexVecini) {
            if (noduri[nodNou].vizitat) continue;
            noduri[nodNou].vizitat = true;
            noduri[nodNou].distanta = noduri[parent].distanta + 1;
            bfsQueue.push(nodNou);
        }
    }
}

int main() {
    citire();
    noduri[S - 1].distanta = 0;
    noduri[S - 1].vizitat = true;
    bfsQueue.push(S - 1);
    BFS();
    for (int i = 0; i < N; i++) {
        fout << noduri[i].distanta << " ";
    }
    return 0;
}