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

using namespace std;

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

#define NMAX 100005

int n, m, s;
queue<int> q;
vector<int> G[NMAX];
int dmin[NMAX];

void citire() {
    f >> n >> m >> s;
    int n1, n2;
    for (int i = 0; i < m; ++i) {
        f >> n1 >> n2;
        G[n1].push_back(n2);
    }
}

void element_nou() {
    int nod = q.front();
    q.pop();
    for (auto &nod2:G[nod])
        if (!dmin[nod2]) {
            dmin[nod2] = dmin[nod] + 1;
            q.push(nod2);
        }
}

void cautare_min() {
    q.push(s);
    dmin[s] = 1;
    while (!q.empty())
        element_nou();
}

void afisare() {
    for (int i = 1; i <= n; ++i)
        g << dmin[i] - 1 << ' ';
}

int main() {
    citire();
    cautare_min();
    afisare();
    return 0;
}