#include <bits/stdc++.h>
using namespace std;

void BFS(int s, vector<vector<int>> &listaVecini, vector<int> &distanta){
    vector<int> vizitat (listaVecini.size(), 0); // vector in care retin nodurile vizitate
    queue<int> coada;   // coada pentru bfs in care retin nodurile care urmeaza sa le parcurg

    vizitat[s - 1] = 1; // pornesc de la nodul de start dat in cerinta
    coada.push(s);  // adaug in coada nodul meu de start

    // cat timp coada nu e goala
    while(coada.empty() == false){
        int nod = coada.front(); // in nod retin nodul curent pe care il parcurg (il scot din coada)
        coada.pop(); // il scot din coada pentru ca l-am parcurs deja

        // adaug in coada fiecare vecin al nodului meu care nu a fost in ca vizitat
        for (int i = 0 ; i < listaVecini[nod - 1].size(); i++){
            if (vizitat[listaVecini[nod - 1][i] - 1] == 0){ // daca nu a fost vizitat
                vizitat[listaVecini[nod - 1][i] - 1] = 1;   // il marchez ca fiind viiztat
                coada.push(listaVecini[nod - 1][i]);    // il adaug in coada
                distanta[listaVecini[nod - 1][i] - 1] = distanta[nod - 1] + 1;  // ii adaug distanta in vectorul de distante
            }
        }
    }

}


int main(){
    ifstream f("bfs.in");
    ofstream g("bfs.out");

    int n, m, s, muchie1, muchie2;
    vector<vector<int>> listaVecini;

    f >> n >> m >> s;

    vector<int> distanta (n , 0); // vectorul in care retin distanta de la nodul s la celelalte noduri

    // initializez lista de vecini
    for (int i = 0; i < n; i++){
        vector<int> aux = {};
        listaVecini.push_back(aux);
    }

    // adaug in lista de vecini muchiile
    for (int i = 0; i < m ; i++){
        f >> muchie1;
        f >> muchie2;
        listaVecini[muchie1 - 1].push_back(muchie2);
    }

    // fac BFS
    BFS(s, listaVecini, distanta);

    // parcurg vectorul distanta si afisez pe ecran distantele
    for (int i = 0 ; i < n; i++){
        // daca distanta este 0 si nodul respectiv nu este nodul de start atunci inseamna ca nu putem sa ajungem la nodul respectiv deci distanta de la s la el este - 1
        if (distanta[i] == 0 && i + 1 != s){
            distanta[i] = -1;
        }
        g << distanta[i] << " ";
   }

    return 0;
}