#include <iostream>
#include <fstream>
#include <deque>
#include <vector>
#include <unordered_map>

using namespace std;

class Graph {
    public:
    unordered_map<int, vector<int> > adj_list;
    
    void add_edge (int n1, int n2) {
        adj_list[n1].push_back(n2);
    }

    void print_ajd_list () {
        for (auto node : adj_list) {
            cout<< "Adj list for node: "<< node.first<< " ";

            for (auto adj_node : node.second) {
                cout<< adj_node << " ";
            }
            cout<<'\n';
        }
    }

};

int main() {
    ifstream fin("bfs.in");
    ofstream fout("bfs.out");
    int nodes, edges, root;
    fin >> nodes;
    fin >> edges;
    fin >> root;

    Graph g;

    for (int i = 0; i < edges; i++) {
        int first, second;
        fin >> first >> second;
        g.add_edge(first, second);
    }

    vector<int> distances (nodes + 1, INT32_MAX);

    deque<int> queue;

    queue.push_back(root);
    distances[root] = 0;

    while (!queue.empty()) {
        int current_root = queue.front();
        queue.pop_front();

        for (auto ajd_node : g.adj_list[current_root]) {
            if (distances[ajd_node] > distances[current_root] + 1) {
                distances[ajd_node] = distances[current_root] + 1;
                queue.push_back(ajd_node);
            }
        }
    }

    for (int i = 1; i < distances.size(); i++) {
        if (distances[i] == INT32_MAX)
            fout<< -1<< " ";
        else fout << distances[i] << " ";
    }
    fout<< '\n';
    return 0;
}