//
// Created by Cristian Constantin on 20.05.2024.
//
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <iterator>

using namespace std;

class Solution {
private:
    size_t n, m, startNode;
    vector<vector<size_t>> graph;

public:
    explicit Solution(ifstream &input) {
        input >> n >> m >> startNode;
        graph.resize(n + 1);

        size_t u, v;
        for (size_t i = 0; i < m; ++i) {
            input >> u >> v;
            graph[u].push_back(v);
        }
    }

    vector<int> bfs() {
        vector<int> distances(n + 1, -1);
        distances[startNode] = 0;

        queue<int> q;
        q.push(startNode);

        int currentDistance = 1;
        int currentLevelNodes = 1;
        int nextLevelNodes = 0;

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

            for (auto neighbor : graph[node]) {
                if (distances[neighbor] == -1) {
                    distances[neighbor] = currentDistance;
                    q.push(neighbor);
                    ++nextLevelNodes;
                }
            }

            if (--currentLevelNodes == 0) {
                currentLevelNodes = nextLevelNodes;
                nextLevelNodes = 0;
                ++currentDistance;
            }
        }

        return distances;
    }
};

int main() {
    ifstream inputFile("bfs.in");
    ofstream outputFile("bfs.out");

    Solution solution(inputFile);
    vector<int> result = solution.bfs();

    copy(result.begin() + 1, result.end(), ostream_iterator<int>(outputFile, " "));

    inputFile.close();
    outputFile.close();

    return 0;
}