#include <fstream>
#include <list>
#include <vector>
#include <queue>

using namespace std;

#ifndef __GRAPH__H
#define __GRAPH__H


// Structura Node este utila doar pentru implementarea cu liste de vecini
struct Node
{
    std::vector<int> neighbors;
};

class Graph {
private:
    std::vector<Node> nodes; // Implementare cu liste de vecini
    // int **adiacency_matrix;  // Implementare cu matrice de adiacenta

public:
    Graph(int size)
    {
        nodes = vector<Node>(size);
    }

    ~Graph()
    {

    }

    //void add_node(int node);    // Atentie: pentru implementarea cu matrice
    //void remove_node(int node); // puteti ignora aceaste doua functii

    void add_edge(int src, int dst)
    {
        nodes[src].neighbors.push_back(dst);
        //nodes[dst].neighbors.push_back(src);
    }
    void remove_edge(int src, int dst)
    {
        int i;
        for (i = 0; i < nodes[src].neighbors.size(); i++)
            if (nodes[src].neighbors[i] == dst)
                nodes[src].neighbors.erase(nodes[src].neighbors.begin() + i);
        for (i = 0; i < nodes[dst].neighbors.size(); i++)
            if (nodes[dst].neighbors[i] == src)
                nodes[dst].neighbors.erase(nodes[dst].neighbors.begin() + i);
    }
    bool has_edge(int src, int dst)
    {
        int i;
        for (i = 0; i < nodes[src].neighbors.size(); i++)
            if (nodes[src].neighbors[i] == dst)
                return true;
        return false;
    }

    std::vector<int> get_neighbors(int node)
    {
        return nodes[node].neighbors;
    }
};

#endif //__GRAPH__H


void bfs(Graph &g, int src, vector<int> &d, vector<bool > &viz)
{
    queue<int> queue;
    viz[src] = true;
    d[src] = 0;
    queue.push(src);
    int node;
   // int neighbor;

    while (!queue.empty()){
        node = queue.front();

        for (int neigh : g.get_neighbors(node)){
            if(!viz[neigh]){
                d[neigh] = d[node] + 1;
                viz[neigh] = true;
                queue.push(neigh);
            }
        }

        queue.pop();

    }

    for (int i = 1; i < viz.size(); i++) {
        if(!viz[i]) {
            d[i] = -1;
        }
    }

}

int main()
{
    int m, n, a, b;
    int s;


    ifstream f("bfs.in");
    ofstream o("bfs.out");

    f >> n >> m >> s;

    Graph g(n + 1);

    vector<int> d(n + 1);
    vector<bool> viz(n + 1, false);


    for (int i = 0; i < m; i++)
    {
        f >> a >> b;
        g.add_edge(a, b);
    }

    bfs(g, s, d, viz);

    for(int k = 1; k <=n; k++){
        o << d[k] <<" ";
    }

    f.close();
    o.close();

    return 0;
}