#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;

class Graph {
    //private attributes
    vector<vector<int>> edges;
    int numberOfNodes;

    //-------------------------------------

    //private methods
public:
    Graph(int);
    ~Graph();
    int getNumberOfNodes();
    void setEdge(int, int);
    void displayEdges();
    vector<int> distance(int);
};


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

    int numberOfNodes, numberOfEdges, start, from, to;

    in >> numberOfNodes >> numberOfEdges >> start;

    Graph* graph = new Graph(numberOfNodes);

    for (int countEdge = 1; countEdge <= numberOfEdges; countEdge++) {
        in >> from >> to;
        graph->setEdge(from, to);
    }

    vector<int> distance = graph->distance(start);

    for (int i = 1; i < distance.size(); i++) {
        out << distance[i] << " ";
    }

    return 0;
}

Graph::Graph(int numberOfNodes) {
    this->numberOfNodes = numberOfNodes;
    this->edges.resize(numberOfNodes + 1);
}

Graph::~Graph() {}

int Graph::getNumberOfNodes() {
    return this->numberOfNodes;
}

void Graph::setEdge(int from, int to) {
    this->edges[from].push_back(to);
}

void Graph::displayEdges() {
    for (int node = 1; node <= this->numberOfNodes; node++)
    {
        cout << node << ": ";
        for (auto edge : this->edges[node])
            cout << edge << " ";
        cout << "\n";
    }
}

vector<int> Graph::distance(int from) {
    queue<int> queue;
    vector<int> visited(this->numberOfNodes + 1, -1);

    visited[from] = 0;
    queue.push(from);

    while (!queue.empty()) {
        int node = queue.front();
        for (auto edge : this->edges[node]) {
            if (visited[edge] == -1) {
                visited[edge] = visited[node] + 1;
                queue.push(edge);
            }
        }
        queue.pop();
    }

    return visited;
}