#include <iostream>
#include <fstream>
#include <bitset>
using namespace std;

#define MAXN 10001

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

int n, m, start;
bitset<MAXN> G[MAXN];
int dist[MAXN];
int q[MAXN], st = 0, dr = 0;

void pushQueue(int nr) {
    q[dr] = nr;
    dr++;
}

void popQueue() {
    st++;
}

int topQueue() {
    return q[st];
}

bool emptyQueue() {
    if (dr - st == 0) {
        return true;
    }
    return false;
}

void bfs() {
    pushQueue(start);
    while (!emptyQueue()) {
        int nd = topQueue();
        popQueue();

        for (int i = 1; i <= n; i++) {
            if (G[nd][i] == 1) {
                if (dist[i] == 0) {
                    dist[i] = dist[nd] + 1;
                    pushQueue(i);
                }
            }
        }
    }
}

int main()
{
    fin >> n >> m >> start;
    for (int i = 1; i <= m; i++) {
        int x, y;
        fin >> x >> y;
        G[x][y] = 1;
    }

    dist[start] = 1;
    bfs();

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

    return 0;
}