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

using namespace std;


void BFS(int vertice, bool visited[], vector<vector<int>> adj, int size) {
    ofstream g("/Users/zamfi/Desktop/AG/dfs/bfs.out");
    int contor = 0;
    int *distanta = new int[size];
    visited[vertice] = true;
    distanta[vertice] = 0;

    list<int> queue;
    queue.push_back(vertice);

    while (!queue.empty()) {
        vertice = queue.front();
        queue.pop_front();
        contor++;

        for (unsigned long i = 0; i < adj[vertice].size(); ++i) {
            if (!visited[adj[vertice][i]]) {
                visited[adj[vertice][i]] = true;
                queue.push_back(adj[vertice][i]);
                distanta[adj[vertice][i]] = contor;
            }
        }

    }

    for (int i = 0; i < size; i++) {
        if (visited[i]) {
            g << distanta[i] << " ";
        } else {
            g << -1 << " ";
        }
    }
}

int main() {
    ifstream f("/Users/zamfi/Desktop/AG/dfs/bfs.in");
    int vertices, i, from, to, edges, nod;
    f>>vertices;
    f>>edges;
    f>>nod;

    nod -= 1;


    bool *visited = new bool[vertices];
    vector<vector<int>> adj((unsigned long) vertices, vector<int> ((unsigned long) vertices));

    for (i = 0; i < vertices; i++) {
        visited[i] = false;
    }

    for (i = 0; i < edges; i++) {
        f >> from; f >> to;
        from -= 1;
        to -= 1;
        adj[from].push_back(to);
    }

    BFS(nod, visited, adj, vertices);
}