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

using namespace std;

int n, m, s;
vector<int>graph[100005];
int lengths[100005];
queue<int> Q;

void bruh(int node){
    for(auto &v : graph[node]){
        if(lengths[v] == 0){
            Q.push(v);
            lengths[v] = lengths[node] + 1;
        }
    }
}

int main() {
    ifstream f("bfs.in");
    ofstream g("bfs.out");
    f>>n>>m>>s;
    for (int i = 0; i < m; ++i) {
        int node, destination;
        f>>node>>destination;
        graph[node - 1].push_back(destination - 1);
    }
    Q.push(s - 1);
    lengths[s - 1] = 1;
    while(!Q.empty()){
        bruh(Q.front());
        Q.pop();
    }
    for (int i = 0; i < n; ++i) {
        g<<lengths[i] - 1<<' ';
    }
    return 0;
}