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

class Graph {
private:
    int nrVertices;
    int nrEdges;
    std::vector<std::vector<int>> g;
public:
    void readGraph(const std::string& inputFile, int &startNode) {
        int firstNode, lastNode;
        std::ifstream fin(inputFile);
        fin >> nrVertices >> nrEdges >> startNode;
        g.resize(nrVertices + 1);
        for(int i = 0; i < nrEdges; ++i) {
            fin >> firstNode >> lastNode;
            g[firstNode].emplace_back(lastNode);
        }
        fin.close();
    }

    void BFS(const int startNode, const std::string& outputFile) {
        std::ofstream fout(outputFile);
        std::vector<int> dist(nrVertices + 1, -1);
        std::queue<int> q;
        int node;
        dist[startNode] = 0;
        q.push(startNode);
        while(!q.empty()) {
            node = q.front();
            q.pop();
            for(auto elem: g[node]) {
                if(dist[elem] == -1) {
                    dist[elem] = 1 + dist[node];
                    q.push(elem);
                }
            }
        }

        for(int i = 1; i <= nrVertices; ++i)
            fout << dist[i] << " ";

        fout << "\n";
        fout.close();
    }
};

int main() {
    Graph G;
    int source;
    G.readGraph("bfs.in", source);
    G.BFS(source, "bfs.out");
    return 0;
}