#include <fstream>
#include <queue>
#include <vector>
#define nmax 100001
using namespace std;

void get_data (int dist[nmax], int &nodes, int &n_edges, int &source, vector <int> edges[nmax]){
    ifstream fin ("bfs.in");
    fin >> nodes >> n_edges >> source;
    for (int i = 1; i <= nodes; i++)
        dist[i] = -1;
    dist [source] = 0;
    for (int i = 1; i <= n_edges; i++){
        int node_1, node_2;
        fin >> node_1 >> node_2;
        edges[node_1].push_back(node_2);
    }
}

void bfs (int source, int nodes, int dist[nmax], vector <int> edges[nmax]){
    queue <int> q;
    q.push (source);
    while (!q.empty ()){
        int current = q.front ();
        q. pop();
        for (auto x : edges[current])
            if (dist[x] == -1){
                dist[x] = dist[current] + 1;
                q.push (x);
            }
    }
}

void output_data (int nodes, int dist[nmax]){
    ofstream fout ("bfs.out");
    for (int i = 1; i <= nodes; i++)
        fout << dist[i] << " ";
}


int main(){
    vector <int> edges[nmax];
    int dist [nmax];
    int nodes, n_edges, source;
    get_data (dist, nodes, n_edges, source, edges);
    bfs (source, nodes, dist, edges);
    output_data (nodes, dist);

    return 0;
}