#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;

vector<int> Dist(vector<vector<int>> la, vector<bool> viz, int s);

void ScriereFisier(vector<int> dist);

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

    int n=0, m=0, s=0, x, y;
    // n = nr de noduri ; m = nr de muchii ; s = nodul initial din bfs
    f>>n>>m>>s;

    // lista_adiac = lista de adiacenta a grafului curent
    vector<int> adiacente;
    vector<vector<int>> lista_adiac(m, adiacente);

    // x,y muchiile citite din fisier
    while(f>>x>>y){
        lista_adiac[x-1].push_back(y-1);
    }

    // viz => tine minte ce nod am vizitat in timpul verificarii
    vector<bool> viz(n, 0);
    
    vector<int> dist = Dist(lista_adiac, viz, s-1);
    ScriereFisier(dist);

    return 0;
}

vector<int> Dist(vector<vector<int>> la, vector<bool> viz, int s){
// dist => distantele de la nodul s la nodul i unde i este indicele in vector
    vector<int> dist(viz.size(), -1);

    // coada de noduri folosita la verificari
    deque<int> c;
    c.push_back(s);
    dist[s]=0;

    while(!c.empty()){
        int nod = c.front();
        c.pop_front();

        viz[nod]=1;

        for(int nod_adiacent : la[nod]){
            // cand am gasit un nod nevizitat il marcam in viz, calculam distanta
            // si il introducem in coada
            if(!viz[nod_adiacent]){

                viz[nod_adiacent]=1;
                c.push_back(nod_adiacent);

                dist[nod_adiacent]=dist[nod]+1;
            }
        }
    }
    return dist;
}
void ScriereFisier(vector<int> dist){
    ofstream g("bfs.out");

    for(int distanta : dist){
        g<<distanta<<" ";
    }
}