#include <fstream>
#include <vector>

using namespace std;
#define DIM 100010


vector<int> L[DIM];
vector<int>::iterator it;

int c[DIM];
int v[DIM];

int n, m, k, i, j, s, p, u, prim;

int main() {
    ifstream fin("bfs.in");
    ofstream fout("bfs.out");
    fin >> n>>m>>s;
    for (k=1;k<=m;k++) {
        fin>>i>>j;
        // adaugam elementul j in lista lui i
        L[i].push_back(j);
//        a[i][j] = 1;
    }

    c[1] = s;
    v[s] = 1;
    p = 1;
    u = 1;

    while (p<=u) {
        // analizez vecinii nevizitati ai lui c[p]
        prim = c[p];
        for (it = L[prim].begin(); it!= L[prim].end(); it++) {
            if (v[ *it ] == 0) {
                u++;
                c[u] = *it;
                v[*it] = v[prim] + 1;
            }
        }
        p++;

    }
    for (i=1;i<=n;i++)
        fout<<v[i]-1<<" ";

    return 0;
}