#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;

class graf{

    vector<vector<int>> adiacenta;

public:
    graf(vector<vector<int>> a): adiacenta(a) {};

    vector<int> bfs(int start){
        vector<int> res(this->adiacenta.size(), -1);
        vector<int> vis(this->adiacenta.size());
        queue<int> q;
        vis[start] = 1;
        q.push(start);
        res[start] = 0;
        while(!q.empty()){
            int curr = q.front();
            q.pop();
            for(int i:adiacenta[curr]){
                if(vis[i] == 0){
                    vis[i] = 1;
                    q.push(i);
                    res[i] = res[curr]+1;
                }
            }
        }
        return res;
    }

};

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

int main(){

    int n, m, s;
    in>>n>>m>>s;
    vector<vector<int>> mat(n);
    for(int i=0; i<m; i++){
        int aux1, aux2;
        in>>aux1>>aux2;
        mat[aux1-1].push_back(aux2-1);
    }
    graf x(mat);
    for(int a:x.bfs(s-1)){
        out<<a<<" ";
    }
    return 0;
}