#include <bits/stdc++.h>

using namespace std;

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

class Graph {

private:

    //Variabile private

    int vertices;
    int edges;
    bool oriented;
    vector<int> *adjacency_list;

    //Functii private

    void BFS(int starting_vertex, int *distances);

    void DFS();

public:

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

    ~Graph();

    void infoarena_graph();

    void solve_distances(int starting_vertex);

};


int main() {
    int N,M,S;

    fin>>N>>M>>S;

    Graph g(N,M,true);
    g.infoarena_graph();

    g.solve_distances(S);
}



Graph::Graph(int vertices, int edges, bool oriented) : vertices(vertices), edges(edges), oriented(oriented) {
    adjacency_list = new vector<int>[vertices + 1];
}

Graph::~Graph() {
    delete[] adjacency_list;
}

void Graph::infoarena_graph() {
    int x, y;
    if (oriented) {
        for (int i = 1; i <= edges; i++) {
            fin >> x >> y;
            adjacency_list[x].push_back(y);
        }
    } else {
        for (int i = 1; i <= edges; i++) {
            fin>>x>>y;
            adjacency_list[x].push_back(y);
            adjacency_list[y].push_back(x);
        }
    }
}

void Graph::BFS(int starting_vertex, int *distances) {

    int* visited = (int*) calloc(vertices+1,sizeof (int));
    queue<int> que;
    que.push(starting_vertex);

    distances[starting_vertex] = 1;
    visited[starting_vertex] = 1;

    while (!que.empty()) {
        int current_node = que.front();
        que.pop();

        for (auto neighbor : adjacency_list[current_node]) {
            if (!visited[neighbor]) {
                que.push(neighbor);
                visited[neighbor] = 1;
                distances[neighbor] = distances[current_node] + 1;
            }
        }
    }

    free(visited);
}

void Graph::solve_distances(int starting_vertex) {
    int *distances = (int*)calloc(vertices+1,sizeof (int));

    BFS(starting_vertex,distances);

    for(int i = 1;i<vertices+1;i++)
        fout<<distances[i] - 1<<' ';

    free(distances);
}