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

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

class Graf{
    private:
        bool orientat;
        int nrNoduri;
        int nrMuchii;
        vector<vector<int>> listaAdiacenta;

        void bfs(vector<int>& distante, vector<bool>& vizitat, int nodStart){
            queue<int> coada;
            coada.push(nodStart);
            distante[nodStart] = 0;

            while (coada.empty() == false){
                int nodCurent = coada.front();
                vizitat[nodCurent] = true;
                for (auto i : listaAdiacenta[nodCurent]){
                    if (vizitat[i] == false){
                        coada.push(i);
                        distante[i] = distante[nodCurent] + 1;
                        vizitat[i] = true;
                    }
                }
                coada.pop();
            }
        }        

        void dfs(vector<bool>& vizitat, int nodCurent){
            vizitat[nodCurent] = true;
            for (auto i : listaAdiacenta[nodCurent])
                if (vizitat[i] == false)
                    dfs(vizitat, i);
        }

    public:
        Graf(){
            nrNoduri = 0;
            nrMuchii = 0;
            orientat = false;
            vector<int> gol;
            for (int i = 0; i < nrNoduri; i++)
                listaAdiacenta.push_back(gol);
        }
        Graf(int nrNod, int nrMuc, bool esteOrientat){
            nrNoduri = nrNod;
            nrMuchii = nrMuc;
            orientat = esteOrientat;            
            vector<int> gol;
            for (int i = 0; i < nrNoduri; i++)
                listaAdiacenta.push_back(gol);
        }

        bool getOrient(){
            return orientat;
        }
        int getNrNoduri(){
            return nrNoduri;
        }
        int getNrMuchii(){
            return nrMuchii;
        }

        void setOrient(bool orient){
            orientat = orient;
        }
        void setNrNoduri(int nr){
            nrNoduri = nr;
        }
        void setNrMuchii(int nr){
            nrMuchii = nr;
        }

        void setareGraf(){
            if (orientat){
                int x, y;
                for(int i = 0; i < nrMuchii; i++){
                    fin >> x >> y;
                    x--;
                    y--;
                    listaAdiacenta[x].push_back(y);
                }
            }
            else{
                int x, y;
                for(int i = 0; i < nrMuchii; i++){
                    fin >> x >> y;
                    x--;
                    y--;
                    listaAdiacenta[x].push_back(y);
                    listaAdiacenta[y].push_back(x);
                }
            }
        }

        vector<int> distanteMinime(int nodStart){
            vector<int> distante(nrNoduri, -1);
            vector<bool> vizitat(nrNoduri, false);

            bfs(distante, vizitat, nodStart);
            return distante;
        }

        int nrCompConexe(){
            int nr = 0;
            vector<bool> vizitat(nrNoduri, false);
            for (int i = 0; i < nrNoduri; i++)
                if (vizitat[i] == false){
                    dfs(vizitat, i);
                    nr++;
                }
            
            return nr;
        }

};

int main(){
    int n, m, nodStart, x, y;
    vector<int> distante;
    vector<vector<int>> lista;
    fin >> n >> m >> nodStart;
    nodStart--;
    Graf graf(n,m,true);
    graf.setareGraf();
    distante = graf.distanteMinime(nodStart);
    for (int i = 0; i < n; i++)
        fout << distante[i] << " "; 
    return 0;
}