#include <vector>
#include <fstream>
#include <queue>
#include <map>
#include <algorithm> // for std::min

#define list std::vector
#define dict std::map

int main()
{
    std::ifstream in("bfs.in");
    std::ofstream out("bfs.out");

    int n, m, s;
    dict<int, list<int>> g;
    dict<int, int> visited;
    dict<int, int> distances;
    std::queue<int> q;
    
    in >> n >> m >> s;
    for (int i = 0; i < m; ++i) {
        int a, b;
        in >> a >> b;
        g[a].push_back(b);
        visited[a] = 0;
        distances[a] = -1;
    }

    // start the queue with something
    q.push(s);
    distances[s] = 0;

    while(!q.empty()) {
        int currentNode = q.front();
        q.pop();

        if (!visited[currentNode]) {
            // print << currentNode << " -> " << distances[currentNode] << '\n';
            visited[currentNode] = 1;
            
            // append its adjacent nodes
            for (auto& n: g[currentNode]) {
                if (!visited[n]) {
                    q.push(n);
                    if (distances[n] != -1) {
                        distances[n] = std::min(distances[n], distances[currentNode] + 1);
                    } else {
                        distances[n] = distances[currentNode] + 1;
                    }
                }
            }
        }
    }

    dict<int, int>::iterator it = distances.begin();
    while (it != distances.end()) {
        out << it->second << " ";
        it ++;
    }

    return 0;
}