#include <bits/stdc++.h>

using namespace std;

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

int N, M, S;
bitset<100005>visited;
vector<vector<int> > adj;
vector<int>dist;

void read(){
    fin >> N >> M >> S;

    dist.resize(N + 1, -1);
    adj.resize(N + 1, vector<int>());
    for (int i = 1, x, y; i <= M; ++i){
        fin >> x >> y;
        adj[x].push_back(y);
    }
}

void bfs(int start){
    queue<pair<int, int> >Q;
    Q.push({start, 0});
    dist[start] = 0;
    visited[start] = 1;

    while(!Q.empty()){
        int k = Q.front().first;
        int d = Q.front().second;
        Q.pop();

        for (int x : adj[k]){
            if (!visited[x]){
                visited[x] = 1;
                dist[x] = d + 1;
                Q.push({x, d + 1});
            }
        }
    }
}

void print(){
    for_each(dist.begin() + 1, dist.end(), [](int el){fout << el << " ";});
}

int main()
{
    read();
    bfs(S);
    print();

    return 0;
}