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

using namespace std;

// functie pentru rezolvarea problemei
void solve() {
    ifstream fin("bfs.in");
    ofstream fout("bfs.out");

    int N, M, S;
    fin >> N >> M >> S;

    // fac lista de adiacenta
    
    vector<vector<int>> adj(N + 1); // graful de la 1 la N
    for (int i = 0; i < M; ++i) {
        int u, v;
        fin >> u >> v;
        adj[u].push_back(v); // marchez un arc orientat de la u la v
    }

    vector<int> dist(N + 1, -1); // vector de distante (initializat cu -1 pt a marca nodurile nevizitate sau inaccesibile)
    queue<int> q; // coada

    // nodul sursa S: distanta 0, adaugat in coada
    dist[S] = 0;
    q.push(S);

    // parcurg bfs
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // iterez prin vecinii (v) ai nodului curent u
        for (int v : adj[u]) {
            // daca nodul v nu a fost vizitat dist e -1
            if (dist[v] == -1) {
                // distanta lui v este distanta lui u + 1
                dist[v] = dist[u] + 1;
                // adaug v in coada ca sa ii vizitez si lui vecinii ulterior
                q.push(v);
            }
        }
    }

    // afisare distanta de la S la nodurile 1 la N
    for (int i = 1; i <= N; ++i) {
        fout << dist[i] << (i == N ? "" : " ");
    }
    fout << endl;
}

//int main() {
//    solve();
//    return 0;
//}