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

using namespace std;


int main(){
    ifstream fin("bfs.in");
    ofstream out("bfs.out");
    
    int n, m, S;
    fin >> n >> m >> S;

    vector<vector<int>> adj(n + 1);
    vector<bool> vizitat(n + 1, false);
    vector<int> dis(n + 1, -1);

    for(int i = 0; i < m; i++){
        int u, v;
        fin >> u >> v;
        adj[u].push_back(v);
    }
    
    queue<int> q;

    q.push(S);
    vizitat[S] = true;
    dis[S] = 0;

    while (!q.empty()){
        int fr = q.front();
        q.pop();
        for(int x : adj[fr]){
            if(!vizitat[x]){
                vizitat[x] = true;
                dis[x] = dis[fr] + 1;
                q.push(x);
            }
        }
    }

    for(int i = 1; i <= n; i++)
        out << dis[i] << " \n"[i == n];
    return 0;
}