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

using namespace std;

ifstream cin ("bfs.in");
ofstream cout ("bfs.out");

const int kNMax = 1000;

/************************** Matrice de adiacenta ********************/

// int n;
// bool edges[kNMax][kNMax];  // false

// void readGraph() {
//     cin >> n;  // numarul de noduri
//     int m; cin >> m;  // numarul de muchii
    
//     for (int i = 0; i < m; i++) {
//         int a, b; cin >> a >> b;  // capetele muchiei
//         a--; b--;
//         edges[a][b] = edges[b][a] = true;
//     }
// }

// void printGraph() {
//     cout << "  ";
//     for (int i = 0; i < n; i++) {
//         cout << i + 1 << " ";
//     }
//     cout << "\n";
    
//     for (int i = 0; i < n; i++) {
//         cout << i + 1 << " ";
//         for (int j = 0; j < n; j++) {
//             cout << edges[i][j] << " ";
//         }
//         cout << '\n';
//     }
//     cout << '\n';
// }

/************************** Liste de adiacenta *********************/

// int n;
// int edges[kNMax][kNMax];
// int grad[kNMax];

// void readGraph() {
//     cin >> n;  // numarul de noduri
//     int m; cin >> m;  // numarul de muchii

//     for (int i = 0; i < m; i++) {
//         int a, b; cin >> a >> b;  // capetele muchiei
//         a--; b--;
        
//         edges[a][grad[a]] = b;
//         grad[a]++;
        
//         edges[b][grad[b]] = a;
//         grad[b]++;
//     }
// }

// void printGraph() {
//     for (int i = 0; i < n; i++) {
//         cout << i + 1 << ": ";
//         for (int j = 0; j < grad[i]; j++) {
//             cout << edges[i][j] + 1 << " ";
//         }
//         cout << "\n";
//     }
//     cout << "\n";
// }

/*********************** Vectori (stl) de adiacenta *********************/

vector<vector<int>> edges;
// vector<bool> viz;
vector<int> dist;
// vector<int> viz;

int readGraph() {
    int n; cin >> n;  // numarul de noduri
    int m; cin >> m;  // numarul de muchii
    int root; cin >> root;  // nodul sursa
    
    edges.resize(n);
    // viz.resize(n);
    dist.resize(n, -1);

    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;  // capetele muchiei
        a--; b--;
        
        edges[a].push_back(b);
        // edges[b].push_back(a);
    }
    
    return root - 1;
}

void printGraph() {
    // for (auto node : edges) {
    //     for (auto next : node) {
    //         cout << node << " " << next << "\n";
    //     }
    // }
    
    for (int i = 0; i < edges.size(); i++) {
        cout << i + 1 << ": ";
        for (int j = 0; j < edges[i].size(); j++) {
            cout << edges[i][j] + 1 << " ";
        }
        cout << "\n";
    }
    cout << "\n";
}

/********************************************** DFS ****************************************/

// // dfs(root)

// void dfs(int node, int comp_conexa) {
//     viz[node] = comp_conexa;
    
//     // for (int i = 0; i < edges[node].size(); i++) {
//     //     int next = edges[node][i];
//     for (auto next : edges[node]) {
//         if (viz[next] == 0) {
//             dfs(next, comp_conexa);
//         }
//     }
// }


/*********************************** BFS ***********************/

void bfs(int node) {
    queue<int> q;
    q.push(node);
    dist[node] = 0;
    // viz[node] = true <=> este in coada sau a fost deja procesat
    
    while (!q.empty()) {
        node = q.front();
        q.pop();
        // cout << node + 1 << " " << dist[node] << "\n";
        
        for (auto next : edges[node]) {
            if (dist[next] == -1) {
                q.push(next);
                dist[next] = dist[node] + 1;;
                // cout << node + 1 << " -> " << next + 1 << '\n';
            }
        }
    }
}


int main() {
    // readGraph();
    int root = readGraph();
    // // printGraph();
    
    bfs(root);
    for (int i = 0; i < dist.size(); i++) {
        cout << dist[i] << " ";
    }
    
    // int count_con = 0;
    // for (int i = 0; i < viz.size(); i++) {
    //     if (viz[i] == 0) {
    //         count_con++;
    //         dfs(i, count_con);
    //     }
    //     cout << i + 1 << " " << count_con << "\n";
    // }
    
    return 0;
}