//
// Created by Catalina Macovei on 28.10.2023.
//
//Fisierul de intrare bfs.in contine pe prima linie 3 numere intregi N M S, cu semnificatia din enunt. Urmatoarele M linii contin cate doua numere x y, cu semnificatia ca exista arc orientat de la x la y.

//In fisierul de iesire bfs.out se vor afla N numere separate prin spatiu cu semnificatia ca al i-lea numar reprezinta numarul minim de arce ce trebuie parcurse de la nodul S la nodul i.
// 1 0 2 -1 1

// Indicatii: Initial, se insereaza nodul S intr-o coada vida, cu costul 0.
// La fiecare pas, se ia nodul din inceputul cozii, se elimina si apoi se adauga vecinii nevizitati la finalul cozii.
// Costul unui nod nou adaugat va fi costul nodului care l-a adaugat + 1.

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

using namespace std;

int main() {
    ifstream fin("laborator1/bfs.in");
    ofstream fout("laborator1/bfs.out");

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

    vector<vector<int>> graf(N + 1);  // Graf reprezentat ca o listă de adiacență
    vector<int> distanta(N + 1, -1);  // Vector pentru distanțe, inițial setate la -1 (infinit)
    queue<int> coada;

    for (int i = 0; i < M; i++) {
        int x, y;
        fin >> x >> y;
        graf[x].push_back(y); // Adăugăm arcele în graf
    }

    // Pasul inițial: adăugăm nodul sursă în coadă
    coada.push(S);
    distanta[S] = 0;

    while (!coada.empty()) {
        int curent = coada.front();
        coada.pop();

        // Parcurgem vecinii nodului curent
        for (int vecin : graf[curent]) {
            if (distanta[vecin] == -1) {  // Dacă nodul nu a fost vizitat încă
                distanta[vecin] = distanta[curent] + 1;
                coada.push(vecin);
            }
        }
    }

    // Scriem rezultatul în fișierul de ieșire
    for (int i = 1; i <= N; i++) {
        if (distanta[i] == -1) {
            fout << "-1 ";
        } else {
            fout << distanta[i] << " ";
        }
    }
    fout << endl;

    fin.close();
    fout.close();

    return 0;
}