#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:
    void citire(){
        ifstream f("../bfs.in");
        vector<int> aux;
        int nrMuchii;

        f>>this->m_nrNoduri;
        this->m_listAdiacenta.assign(this->m_nrNoduri + 1, 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();
            for(int i=0; i < this->m_listAdiacenta[curent].size(); 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 prelucrareDFS(int nod){
        cout<<nod<<endl;
    }

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

        for(int i=0; i<this->m_listAdiacenta[nod].size(); i++){
            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;

    g.citire();

    g.BFS(nodSursa);
    
    g.afisDrumuri();
    return 0;
}