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

using namespace std;

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

struct Edge
{
    int source;
    int destination;
    int cost;

    Edge(int source = 0,int destination = 0,int cost = 0):
        source(source),
        destination(destination),
        cost(cost) { }
};


class Graph{

private:

    //private variables
    int vertices, edges;
    bool oriented, weighted;
    vector<vector<Edge>> adjacency_list;

    //To compute:
    vector<int> distances;
    vector<list<int>> biconnected_components;
    vector<vector<int>> strongly_connected_components;
    vector<int> topological;
    vector<pair<int,int>> bridges;

    //private functions

    void BFS(int starting_vertex);

    void DFS(int vertex, int* visited);

    void BCC();
    void SCC();
    void CCN();

    void TOPOLOGICAL_SORT();

    vector<int> BFSMD(int starting_vertex);

public:
    Graph(int vertices = 0,int edges = 0,bool oriented = false,bool weighted = false);

    void infoarena_graph();

    void show_my_graph();

    void solve_distances(int starting_vertex);

    void solve_connected_components();

    void solve_biconnected();

    void solve_strongly_connected();

    void solve_topological();

    void solve_critical_connections();

    void solve_starting_ending_distance(int starting_vertex,int ending_vertex);
};

void printv(vector<int> xs){
    for(int i : xs) cout<<i<<' ';
    cout<<'\n';
}

int main()
{
    int n, m, s;
    fin>>n>>m>>s;
    Graph g(n,m);
    g.infoarena_graph();

    g.solve_distances(s);
}

Graph::Graph(int vertices, int edges, bool oriented, bool weighted) :
    vertices(vertices),
    edges(edges),
    oriented(oriented),
    weighted(weighted)
{
    adjacency_list.resize(vertices + 1);
}

void Graph::infoarena_graph() {
    int x,y;
    int c = 0;
    for(int i = 1;i<=edges;i++)
    {
        fin>>x>>y;

        if(weighted)
            fin>>c;

        adjacency_list[x].push_back(Edge(x,y,c));

        if(oriented)
            adjacency_list[y].push_back(Edge(y,x,c));
    }
}

void Graph::show_my_graph() {
    for(int i = 1;i<=vertices;i++){
        cout<<i<<"=>";
        for(auto path : adjacency_list[i])
            cout<<path.destination<<' ';
        cout<<'\n';
    }
}

void Graph::BFS(int starting_vertex)
{

    distances.resize(vertices+1,-1);
    queue<int> que;
    que.push(starting_vertex);
    distances[starting_vertex] = 0;
    while(!que.empty()){
        int vert = que.front();
        que.pop();
        for(auto path : adjacency_list[vert])
            if(distances[path.destination] == -1){
                que.push(path.destination);
                distances[path.destination] = distances[vert] + 1;
            }
    }
}

void Graph::solve_distances(int starting_vertex) {
    BFS(starting_vertex);
    for(int i = 1;i<vertices+1;i++)
        fout<<distances[i]<<' ';
}