#include <iostream>
#include <string.h>
#include <vector>
#include <fstream>
using namespace std;

ifstream f ("bfs.in");
ofstream g ("bfs.out");

int N, M, i, nod1, nod2, distanta[100001], coada[100001], prim, ultim, start;
vector <int> muchii[100001];
void BFS();

void citire () {
    f >> N >> M >> start;
    for (i = 1; i <= M; i++) {
        f >> nod1 >> nod2;
        muchii[nod1].push_back(nod2);
    }
    //memset(distanta, -1, N);
    for (i = 1; i <= N; i++)
        distanta[i] = -1;
    distanta[start] = 0;
    prim = 1; ultim = 1;
    coada[1] = start;
    BFS();
}

void BFS() {
    int nod, vecin;
    while (prim <= ultim) {
        nod = coada[prim];
        prim++;
        for (i = 0; i < muchii[nod].size(); i++) {
            vecin = muchii[nod][i];
            if (distanta[vecin] == -1) {
                distanta[vecin] = distanta[nod] + 1;
                ultim++;
                coada[ultim] = vecin;
            }
        }
    }
}

int main() {
    citire();
    for (i = 1; i <= N; i++)
        g << distanta[i] << " ";
    return 0;
}