#include <stdio.h>
#include <vector>
#include <string.h>
#include <iostream>
#include <fstream>
#include <queue>
 
#define NMAX 100005
int cost[NMAX], n, m;
std::vector<int> neighbors[NMAX];

void bfs (int source) {
    std::queue<int> BFSQueue;
    BFSQueue.push(source);
    cost[source] = 0;
    int node;

    while (!BFSQueue.empty()) {
        node = BFSQueue.front();
        BFSQueue.pop();
        for (unsigned int i = 0; i < neighbors[node].size(); i++) {
            if (cost[neighbors[node][i]] == -1) { // if it's not visited
                BFSQueue.push(neighbors[node][i]);
                cost[neighbors[node][i]] = cost[node] + 1;
            }
        }
    }
}   
 
int main() {
    std::ifstream fin("bfs.in");
    std::ofstream fout("bfs.out");
 
    int i, x, y, start;
 
    fin >> n >> m >> start;
  
    for (i = 1; i <= m; i++) 
    {
        fin >> x >> y;
        neighbors[x].push_back(y);
    }
 
    memset(cost, -1, NMAX * sizeof(int));
    bfs(start);
 
    for (i = 1; i <= n; i++) 
        fout << cost[i] << ' ';
    fout << "\n";
    return 0;
}