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

using namespace std;
// Face BFS in graful cu lista de adiacenta adj, node = nodul de START, cnt = numarul de noduri vizitate
void bfs(vector<vector<int>>& adj, int node, vector<bool>& visited, int dist[]) {
    queue<int> q;
    visited[node] = true;
    q.push(node);
    dist[node] = 0;
    while(!q.empty()) {
        int tempNode = q.front();
        q.pop();
        for(int i = 0; i < adj[tempNode].size(); i++) {
            if(!visited[adj[tempNode][i]]) {
                visited[adj[tempNode][i]] = true;
                q.push(adj[tempNode][i]);
                dist[adj[tempNode][i]] = dist[tempNode] + 1;
            }
        }
    }
}

int main() {
    ifstream fin("bfs.in");
    ofstream fout("bfs.out");
    int n, m, s;
    fin >> n >> m >> s;
    int distance[100005]; // vector de frecventa in care pun distanta de la nodul de start la nodul i
    for(int i = 1; i <= n; i++)
        distance[i] = -1; // initializez vectorul de distante cu -1
    vector<vector<int>> adj(n+1);
    vector<bool> visited(n+1, false);
    for(int i = 0; i < m; i++){
        int u, v;
        fin >> u >> v;
        adj[u].push_back(v);
    }
    bfs(adj, s, visited, distance);
    for(int i = 1; i <= n; i++)
        cout << distance[i] << " ";
}






































// void bfs(vector<vector<int>>& adj, int s, vector<bool>& visited, vector<int>& dist, vector<int>& prev) {
//     int n = adj.size();
//     visited.assign(n, false);
//     dist.assign(n, -1);
//     prev.assign(n, -1);
//     queue<int> q;
//     visited[s] = true;
//     dist[s] = 0;
//     q.push(s);
//     while (!q.empty()) {
//         int u = q.front();
//         q.pop();
//         for (int v : adj[u]) {
//             if (!visited[v]) {
//                 visited[v] = true;
//                 dist[v] = dist[u] + 1;
//                 prev[v] = u;
//                 q.push(v);
//             }
//         }
//     }
// }