#include<iostream>
#include<queue>
#include<vector>
#include<fstream>
#include<queue>

using namespace std;

class Graph{
    private:
        int numberOfNodes = 0;
        int numberOfEdges = 0;
        vector<int> nodes;
        vector<vector<int>> neighbours;


    public:
        Graph(int n);
        Graph() {};
        int getNumberOfNodes() {return this->numberOfNodes;};
        void addDirectedEdge(int a, int b);
        void addUndirectedEdge(int a, int b);
        void bfs(int node);
        vector<int> bfs_cost(int node);
        void dfs(int node);
        int NumberOfConnectedComponets();
};

Graph::Graph(int n){
    this->numberOfNodes = n;
    for(int i = 0; i <=n; i++)
        this->neighbours.push_back(vector<int>());
}

void Graph::addUndirectedEdge(int a, int b){
    this->neighbours[a].push_back(b);
    this->neighbours[b].push_back(a);
    this->numberOfEdges++;
}

void Graph::addDirectedEdge(int a, int b){
    this->neighbours[a].push_back(b);
    this->numberOfEdges++;
}

void Graph::bfs(int node){
    vector<int> visited(this->getNumberOfNodes() + 1);
    queue<int> q;

    q.push(node);
    visited[node] = 1;

    while(!q.empty()) {
        int currentNode = q.front();
        cout<<currentNode<<" ";
        q.pop();
        for(int i: this->neighbours[currentNode]) {
            if(!visited[i]) {
                q.push(i);
                visited[i] = 1;
            }
        }
    }
    cout<<"\n";
}

vector<int> Graph::bfs_cost(int node){
    vector<int> visited(this->getNumberOfNodes() + 1);
    queue<int> q;
    vector<int> cost(this->getNumberOfNodes() + 1);

    q.push(node);
    visited[node] = 1;

    while(!q.empty()) {
        int currentNode = q.front();
        q.pop();
        for(int i: this->neighbours[currentNode]) {
            if(!visited[i]) {
                q.push(i);
                cost[i] = cost[currentNode] + 1;
                visited[i] = 1;
            }
        }
    }

    for(int i = 1; i <= this->getNumberOfNodes(); i++){
        if(!visited[i])
            cost[i] = -1;
    }

    return cost;
}

int main() {
    int n, m, startNode;

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

    fin >> n >> m >> startNode;

    Graph graph = Graph(n);

    for(int i = 1; i <= m; i ++)
    {
        int a, b;
        fin >> a >> b;
        graph.addDirectedEdge(a,b);
    }

    vector<int> result = graph.bfs_cost(startNode);

    for(int i = 1; i < result.size(); i++)
        fout<<result[i]<<" ";

    return 0;
}