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

int numarNoduri, numarMuchii, nod_start;

std::vector<std::vector<int>> MemoGrafLista(int tip){
    int i, j;
    std::ifstream fin;
    fin.open("bfs.in");
    if (!fin.is_open()){
        std::cout << "Eroare - fisierul nu este deschis \n";
    }
    else {
        fin >> numarNoduri >> numarMuchii;
        fin >> nod_start;
        //creez n liste vide
        std::vector<std::vector<int>> liste_adiacenta(numarNoduri + 1);
        for (int cnt = 0; cnt < numarMuchii; cnt++) {
            fin >> i >> j;
            liste_adiacenta[i].push_back(j);
            if(tip == 0)
                liste_adiacenta[j].push_back(i);
        }
        //std::cout << "Memorat cu succes.\n";

        //sortez crescator listele de adiacenta
        for(int nod = 1; nod <= liste_adiacenta.size() - 1; nod++){
            std::sort(liste_adiacenta[nod].begin(), liste_adiacenta[nod].end());
        }
        //std::cout << "S-a memorat ca lista.\n";
        return liste_adiacenta;
    }
}

void bfsDistante(std::vector<std::vector<int>> &graf, int s){
    int inf = 2147483647;
    std::vector<int> dist(graf.size(), inf);
    int nod_crt;
    std::vector<int> viz(graf.size(), 0);
    std::queue<int> myqueue;
    myqueue.push(s);
    viz[s] = 1;
    dist[s] = 0;
    while(!myqueue.empty()){
        nod_crt = myqueue.front();
        myqueue.pop();
        //std::cout << nod_crt << " ";
        for(auto vecin : graf[nod_crt]){
            if(viz[vecin] ==0){
                myqueue.push(vecin);
                viz[vecin] = 1;
                dist[vecin] = dist[nod_crt] + 1;
            }
        }
    }
    std::ofstream fout("bfs.out");
    for(int cnt = 1; cnt <= numarNoduri; cnt++){
        if(dist[cnt] == inf)
            fout << -1 << " ";
        else
            fout << dist[cnt] << " ";
    }
}


int main() {
    //std::cout << "Tipul de graf (0 - neorientat, 1 - orientat) \n";
    //int n; std::cin >> n;
    std::vector<std::vector<int>> listeAdiacenta;
    listeAdiacenta = MemoGrafLista(1);
    bfsDistante(listeAdiacenta, nod_start);

    return 0;
}