#include <bits/stdc++.h>


using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");
class Graph{

private:

    int nodes, edges, starting_node;
    int* color;  //3 color 0 -> white, 1 -> gray, 2 -> black
    int* distances;
    vector<int>* preds; //not using yet
    vector<int>* adjacency_list;

    bool oriented;

public:
    Graph(int nodes = 0, int edges = 0,int starting_node = 0, bool oriented = true):
            nodes(nodes), edges(edges), oriented(oriented), starting_node(starting_node)
    {

        color = new int[nodes + 1];
        distances = new int[nodes+1];
        preds = new vector<int>[nodes+1];
        adjacency_list = new vector<int>[nodes+1];

        for(int i = 0;i<nodes+1;i++)
            color[i] = 0;

        for(int i = 0;i<nodes+1;i++)
            distances[i] = 0;
    }

    ~Graph(){
        delete[] color;
        delete[] distances;
        delete[] preds;
        delete[] adjacency_list;
    }

    int getNodes() const {
        return nodes;
    }

    void setNodes(int nodes) {
        nodes = nodes;
    }

    int getEdges() const {
        return edges;
    }

    void setEdges(int edges) {
        edges = edges;
    }


    void setColors(int *colors) {
        Graph::color = colors;
    }


    void setDistances(int *distances) {
        Graph::distances = distances;
    }

    vector<int> *getPreds() const {
        return preds;
    }

    void setPreds(vector<int> *preds) {
        Graph::preds = preds;
    }

    vector<int> *getAdjacencyList() const {
        return adjacency_list;
    }

    void setAdjacencyList(vector<int> *adjacencyList) {
        adjacency_list = adjacencyList;
    }

    bool isOriented() const {
        return oriented;
    }

    void setOriented(bool oriented) {
        Graph::oriented = oriented;
    }

    void set_graph(){
        int x,y;
        for(int i = 1;i<=edges;i++){
            fin>>x>>y;
            adjacency_list[x].push_back(y);
        }
    }

    void show_graph() {
        for (int i = 1; i <= nodes; i++) {
            cout << i << ":";
            for (int neighbor : adjacency_list[i]) {
                cout << neighbor << ' ';
            }
            cout << '\n';
        }
    }

    void show_distances()
    {
        BFS();
        for(int i = 1;i<nodes+1;i++){
            fout<<distances[i] - 1<<' ';
        }
    }


private:

    void BFS(){
        queue<int> que;
        que.push(starting_node);

        color[starting_node] = 1;
        distances[starting_node] = 1;

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

            for(int neighbor : adjacency_list[node])
            {
                if(color[neighbor] == 0)
                {
                    que.push(neighbor);
                    color[neighbor] = 1;
                    distances[neighbor] = distances[node] + 1;
                }
            }

            color[node] = 2;
        }
        
    }

};



int main() {

    int n,m,s;

    fin>>n>>m>>s;

    Graph g(n,m,s);

    g.set_graph();

    g.show_distances();
    return 0;
}