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

const int maxi = 10010;
vector<int> lista[maxi];
int g[maxi], coada[maxi], cost[maxi];

void BFS(int start, int lungime, int n) {
    int i, j;
    for(i = 0; i < maxi; ++i)
        cost[i] = -1;
    cost[start] = 0;
    coada[lungime] = start;
    for(i = 1; i <= lungime; ++i)
        for(j = 0; j < g[coada[i]]; ++j)
            if(cost[lista[coada[i]][j]] == -1) {
                coada[++lungime] = lista[coada[i]][j];
                cost[coada[lungime]] = cost[coada[i]] + 1;
            }
}

int main() {
    ifstream fin("bfs.in");
    ofstream fout("bfs.out");
    int n, m, i, j, x, y, lungime, start;
    lungime = 1;
    fin >> n >> m >> start;
    for(i = 1; i <= m; ++i) {
        fin >> x >> y;
        lista[x].push_back(y);
    }
    for(i = 1; i <= n; ++i)
        g[i] = lista[i].size();
    BFS(start, lungime, n);
    for(i = 1; i <= n; ++i)
        fout << cost[i] << " ";
    return 0;
}