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

using namespace std;

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

vector<vector<int>> listaMuchii;
vector<int> viz;
vector<int> dist;

void bfs(int nodInceput) {
    queue<int> coada;
    coada.push(nodInceput);
    viz[nodInceput] = 1;
    while (!coada.empty()) {
        int nodCurent = coada.front();
        coada.pop();
        for (int nod : listaMuchii[nodCurent]) {
            if (viz[nod] == 0) {
                viz[nod] = 1;
                dist[nod] = dist[nodCurent] + 1;
                coada.push(nod);
            }
        }
    }
}

int main() {
    int n,m,s;
    fin >> n >> m >> s;

    listaMuchii.resize(n+1);
    viz.resize(n+1, 0);
    dist.resize(n+1, -1);

    for (int i=1; i<=m; i++) {
        int a,b;
        fin >> a >> b;
        listaMuchii[a].push_back(b);
    }

    dist[s] = 0;
    bfs(s);

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

}