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

using namespace std;

int nodSursa;
int distante[100001];

class Graf {
private:
    int m_nrNoduri;
    vector<vector<int>> m_listAdiacenta;
public:
    /*friend istream &operator>>(istream &in, Graf &graf) {
        ifstream f("../bfs.in");
        vector<int> aux;
        int nrMuchii;

        f>>graf.m_nrNoduri;
        graf.m_listAdiacenta.assign(graf.m_nrNoduri + 1, aux);

        f>>nrMuchii;

        f>>nodSursa;

        for(int i=0; i<nrMuchii; i++){
            int x,y;
            f>>x>>y;
            graf.m_listAdiacenta[x].push_back(y);
        }
    }
    friend ostream &operator<<(ostream &out, Graf &graf) {
        ofstream g("../date.out");
        for(int i=1; i<=graf.m_nrNoduri; i++){
        //    g<<i<<": ";
            cout<<i<<": ";
            for(int j=0; j<graf.m_listAdiacenta[i].size(); j++){
          //      g<<graf.m_listAdiacenta[i][j]<<" ";
                cout<<graf.m_listAdiacenta[i][j]<<" ";
            }
            //g<<"\n";
            cout<<"\n";
        }
    }*/
    void citire(){
        ifstream f("../bfs.in");
        vector<int> aux;
        int nrMuchii;

        f>>this->m_nrNoduri;
        this->m_listAdiacenta.assign(this->m_nrNoduri + 10, aux);

        f>>nrMuchii;

        f>>nodSursa;

        for(int i=0; i<nrMuchii; i++){
            int x,y;
            f>>x>>y;
            this->m_listAdiacenta[x].push_back(y);
        }
    }
    void prelucrare(int nod, int x){
        //cout<<nod<<"\n";
        distante[nod] = distante[x] + 1;
    }
    void BFS(int nod){
        int curent;
        queue<int> coada;
        int viz[this->m_nrNoduri+1];
        for(int i=1; i<=m_nrNoduri; i++){
            viz[i] = 0;
        }

        coada.push(nod);
        viz[nod] = 1;
        prelucrare(nod, nod);

        while(!coada.empty()){
            curent = coada.front();
            //cout<<endl<<curent<<": ";
            for(int i=0; i < this->m_listAdiacenta[curent].size(); i++){
               // cout<<this->m_listAdiacenta[curent][i]<<" ";
                if(viz[this->m_listAdiacenta[curent][i]] == 0){
                    coada.push(this->m_listAdiacenta[curent][i]);
                    prelucrare(coada.back(),curent);
                    viz[this->m_listAdiacenta[curent][i]] = 1;
                }
            }
            coada.pop();
        }

    }

    void prelucrareTest(int nod){
        cout<<nod<<"\n";
    }

    void parcurgeAdancime(int nod, int viz[]){
        prelucrareTest(nod);
        viz[nod] = 1;

        for(int i=0; i<this->m_listAdiacenta[nod].size(); i++){
            //cout<<this->m_listAdiacenta[nod][i]<<"-"<<viz[this->m_listAdiacenta[nod][i]]<<endl;
            if(viz[this->m_listAdiacenta[nod][i]] == 0){
                parcurgeAdancime(this->m_listAdiacenta[nod][i],viz);
            }
        }
    }

    void DFS(int nod){
        int viz[this->m_nrNoduri+1];
        for(int i=1; i<=m_nrNoduri; i++){
            viz[i] = 0;
        }
        parcurgeAdancime(nod,viz);
    }

    void afisDrumuri() {
        ofstream g("../bfs.out");
        for(int i=1; i <= this->m_nrNoduri; i++){
            g<<distante[i] - 1<<" ";
        }
    }
};

int main() {
    Graf g;
    //cin>>g;
    g.citire();
    /*cout<<g;

    cout<<"--------------------------------\n";*/

    g.BFS(nodSursa);
    /*cout<<"--------------------------------\n";
    g.DFS(1);*/

    g.afisDrumuri();
    return 0;
}