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

class Graph {
    int nrNodes, nrEdges;
    vector<vector<int>> edges;
public:
    Graph(int nrNodes) ;
    void addEdge(int x, int y); // sets edge between x and y
    void BFS(int startingNode, ostream& g);
    ~Graph();
};
Graph::Graph(int nrNodes) {
    this->nrNodes = nrNodes;
    edges.resize(nrNodes + 1);
}
void Graph::addEdge(int x, int y) {
    this->edges[x].push_back(y);
}
void Graph::BFS(int startingNode, ostream& g) {
    vector<int> cost(this->nrNodes+1, -1);
    vector<int> visited(this->nrNodes+1, 0);
    queue<int> queue;
    cost[startingNode] = 0;
    visited[startingNode] = 1;
    queue.push(startingNode);
    while(!queue.empty()){
        int currentNode = queue.front();
        for(auto node : edges[currentNode]){
            if(!visited[node]){
                visited[node] = 1;
                cost[node] = cost[currentNode] + 1;
                queue.push(node);
            }
        }
        queue.pop();
    }
   for(int i = 1; i<= nrNodes; i++ ){
       g << cost[i] << " ";
   }
}
Graph::~Graph(){
    edges.clear();
}
int main()
{
    ifstream f("bfs.in");
    ofstream g("bfs.out");
    int nrNodes, nrEdges, startingNode;
    f >> nrNodes >> nrEdges >> startingNode;
    Graph G(nrNodes);
    for(int i = 1; i<= nrEdges; i++) {
        int x, y;
        f >> x >> y;
        G.addEdge(x,y);
    }
    G.BFS(startingNode, g);
    
}