// #include <bits/stdc++.h>
// using namespace std;
// const int nmax = 10000;
// vector<int> a[nmax + 1];
// int n, m, s, x, y;       
// const int INF = INT_MAX; //val pt a reprezenta nodurile inaccesibile
// int d[nmax + 1];         // Distanta de la nodul sursa la nodul i
// queue<int> q;             // Coada

// int main() {
//     ifstream f("bfs.in");
//     f >> n >> m >> s;
//     while (m--) {
//         f >> x >> y;
//         a[x].push_back(y);
//     }
//     f.close();

//     //initializam distantele cu INF pentru a marca nodurile inaccesibile
//     for (int i = 1; i <= n; i++) {
//         d[i] = INF;
//     }

//     // Parcurgere BFS
//     q.push(s);
//     d[s] = 0;

//     while (!q.empty()) {
//         int x = q.front();
//         q.pop();
//         for (int i = 0; i < a[x].size(); i++) {
//             int y = a[x][i];
//             if (d[y] == INF) { //verificam ca nodul sa nu fi fost vizitat deja
//                 d[y] = d[x] + 1;
//                 q.push(y);
//             }
//         }
//     }

//     ofstream fout("bfs.out"); // output file
//     //scriem distantele in fisier
//     for (int i = 1; i <= n; i++) {
//         if (d[i] == INF) {
//             fout << -1 << " "; // nod in care nu putem ajunge
//         } else {
//             fout << d[i] << " ";
//         }
//     }
//     fout << endl;
//     fout.close(); 

//     return 0;
// }

#include <bits/stdc++.h>
using namespace std;
const int nmax = 10000;
vector<int> a[nmax + 1]; // Doar pentru lista de adiacenta
int n, m, s, x, y;       // LFL
const int INF = INT_MAX; // Special value to represent unreachable nodes
int d[nmax + 1];         // Distanta de la nodul sursa la nodul i
queue<int> q;             // Coada

int main() {
    ifstream f("bfs.in");
    f >> n >> m >> s;
    while (m--) {
        f >> x >> y;
        a[x].push_back(y);
    }
    f.close();

    // Initialize distances with INF to mark unreachable nodes
    for (int i = 1; i <= n; i++) {
        d[i] = INF;
    }

    // Parcurgere BFS
    q.push(s);
    d[s] = 0;

    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (size_t i = 0; i < a[x].size(); i++) {
            int y = a[x][i];
            if (d[y] == INF) { // Check if the node is not visited yet
                d[y] = d[x] + 1;
                q.push(y);
            }
        }
    }

    ofstream fout("bfs.out"); // Open the output file
    // Write the distances to the output file
    for (int i = 1; i <= n; i++) {
        if (d[i] == INF) {
            fout << -1 << " "; // Node is unreachable
        } else {
            fout << d[i] << " ";
        }
    }
    fout << endl;
    fout.close(); // Close the output file

    return 0;
}