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

using namespace std;
ifstream cin ("bfs.in");
ofstream cout ("bfs.out");

const int NMAX = 1e5;

struct nod{
    vector<int> vecini;
};

int n, m, start;
int sol[NMAX + 1];
nod graf[NMAX + 1];
queue<int> q;
bitset<NMAX + 1> vizitat;

void citire(){
    cin >> n >> m >> start;
    for (int i = 1; i <= m; ++i){
        int x, y;
        cin >> x >> y;
        graf[x].vecini.push_back(y);
    }
}

void preinit(){
    for (int i = 1; i <= n; ++i){
        sol[i] = -1;
    }
}

void bfs(){
    q.push(start);
    sol[start] = 0;

    while (! q.empty()){
        int x = q.front();
        q.pop();
        vizitat[x] = true;
        for (auto a : graf[x].vecini){
            if (! vizitat[a]){
                q.push(a);
                sol[a] = sol[x] + 1;
            }
                
        }
    }
}

void afisare(){
    for (int i = 1; i <= n; ++i){
        cout << sol[i] << ' ';
    }
}

int main(){
    citire();
    preinit();
    bfs();
    afisare();
    return 0;
}