#include <algorithm>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

vector <int> bfs(int startingNode, vector < vector <int> > &graph) {
    queue <int> Queue;
    vector <int> distances (graph.size(), -1);
    Queue.push(startingNode);
    distances[startingNode] = 0;
    while (!Queue.empty()) {
        auto currentNode = Queue.front();
        Queue.pop();

        for (auto &neighbour : graph[currentNode]) {
            if (distances[neighbour] == -1 or distances[neighbour] > distances[currentNode] + 1) {
                distances[neighbour] = distances[currentNode] + 1;
                Queue.push(neighbour);
            }
        }
    }
    reverse(distances.begin(), distances.end());
    distances.pop_back();
    reverse(distances.begin(), distances.end());
    return distances;
}

int main() {
    ifstream cin ("bfs.in");
    ofstream cout ("bfs.out");
    int numberOfNodes, numberOfEdges, startingNode;
    cin >> numberOfNodes >> numberOfEdges >> startingNode;
    vector < vector <int> > graph(numberOfNodes + 1);
    for (int index = 0; index <= numberOfEdges; ++ index) {
        int nodeOne, nodeTwo;
        cin >> nodeOne >> nodeTwo;
        graph[nodeOne].push_back(nodeTwo);
    }
    auto result = bfs(startingNode, graph);
    for (auto &elem : result) {
        cout << elem << ' ';
    }
    return 0;
}