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

using namespace std;

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

#define NMAX 100001
#define MMAX 1000005

class Graf{
    vector<int> nod[NMAX];
    vector<int> viz;
    queue<int> coada;
    int nrNoduri, nrMuchi;
    bool orientat = false, neorientat = false;

    void setOrientat(bool orientat = true){
        if(orientat) this->orientat = true, this->neorientat = false;
        else this->orientat = false, this->neorientat = true;
    }

    void setNeorientat(bool neorientat = true){
        if(neorientat) this->neorientat = true, this->orientat = false;
        else this->neorientat = false, this->orientat = true;
    }

    void setViz(int nod, int val){
        this->viz.assign(nod + 1, val);
    }
public:

    void citire(int nrNoduri, int nrMuchi, vector<pair<int, int>> muchi, bool orientat = true){
        if(orientat) setOrientat();
        else setNeorientat();
        this->nrNoduri = nrNoduri;
        this->nrMuchi = nrMuchi;
        for(auto i : muchi){
            this->nod[i.first].push_back(i.second);
            if(this->neorientat) this->nod[i.second].push_back(i.first);

        }
    }

    void actBFS(int S);
    vector<int> BFS(int S);

};
void Graf::actBFS(int S){
    this->coada.push(S);
    this->viz[S] = 0;
    while(!coada.empty()){
        int current = coada.front();
        coada.pop();
        int dist = viz[current] + 1;
        for(auto vecin : nod[current]){
            if(viz[vecin] == -1){
                viz[vecin] = dist;
                coada.push(vecin);
            }
        }
    }
}

vector<int> Graf::BFS(int S){
    setViz(this->nrNoduri, -1);
    actBFS(S);
    return this->viz;
}

Graf graf;
void rezolvareBFS(){
    vector<pair<int, int>> muchi;
    int n, m, s;
    fin>>n>>m>>s;
    for(int i = 1; i <= m; i++){
        int x, y;
        fin>>x>>y;
        muchi.push_back(make_pair(x, y));
    }
    graf.citire(n, m, muchi);
    vector<int> sol = graf.BFS(s);
    for(int i = 1; i <= n; i++){
        fout<<sol[i]<<" ";
    }
}

int main(){
    rezolvareBFS();
}