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

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

#define VI vector<int>
#define VB vector<bool>
#define QI queue<int>
#define VVI vector<VI>
#define pb push_back

int N, M;
VVI adList;
VB vis;
VI dist;

void BFS(QI &coada, VB &vis);
void print();

int main() {
    int S;
    fin >> N >> M >> S;
    adList = VVI(N + 1);
    dist = VI(N + 1, -1);
    for (int i = 0; i < M; ++i) {
        int x, y;
        fin >> x >> y;
        adList[x].pb(y);
    }
    QI coada;
    vis = VB(N + 1, false);
    coada.push(S);
    vis[S] = true;
    dist[S] = 0;
    BFS(coada, vis);
    print();
}

void print() {
    for (int nod = 1; nod <= N; ++nod) {
        fout << dist[nod] << ' ';
    }
}

void BFS(QI &coada, VB &vis) {
    if (coada.empty()) {
        return;
    }
    int nod = coada.front();
    coada.pop();
    for (auto vecin : adList[nod]) {
        if (!vis[vecin]) {
            vis[vecin] = true;
            coada.push(vecin);
            dist[vecin] = dist[nod] + 1;
        }
    }
    BFS(coada, vis);
}