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

using namespace std;

class Graph {
public:
    Graph();
    void findShortestDistances();
    void showResult();
private:
    void initGraph();
    void initDistances();
    bool isUniqueEdge(int, int);
    vector<vector<int> > graph;
    vector<int> distances;
    int start;
    ifstream in;
    ofstream out;
};

Graph::Graph() {
    in .open("bfs.in" );
    out.open("bfs.out");

    initGraph();
    initDistances();
}

void Graph::initGraph() {
    unsigned long long nodes, edges;
    in >> nodes >> edges >> start;
    graph.resize(nodes + 1);

    for (int pairIndex = 0; pairIndex < edges; pairIndex++) {
        int left, right;
        in >> left >> right;

        if (left != right && isUniqueEdge(left, right)) {
            graph[left].push_back(right);
        }
    }
}

bool Graph::isUniqueEdge(int left, int right) {
    vector<int>::iterator rightIndex =
        find(graph[left].begin(), graph[left].end(), right);
    return rightIndex == graph[left].end();
}

void Graph::initDistances() {
    distances.resize(graph.size());
    fill(distances.begin(), distances.end(), -1);
    distances[start] = 0;
}

void Graph::findShortestDistances() {
    vector<int> queue;
    queue.push_back(start);

    for (int index = 0; index < queue.size(); index++) {
        int node = queue[index], neighborIndex = 0;
        
        for (; neighborIndex < graph[node].size(); neighborIndex++) {
            int neighbor = graph[node][neighborIndex];
            if (distances[neighbor] != -1) {
                continue;
            }

            distances[neighbor] = distances[node] + 1;
            queue.push_back(neighbor);
        }
    }
}

void Graph::showResult() {
    for (int index = 1; index < distances.size(); index++) {
        out << distances[index] << ' ';
    }
}

int main() {
    Graph graph;
    graph.findShortestDistances();
    graph.showResult();

    return 0;
}