#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin ("bfs.in");
ofstream fout ("bfs.out");

class Graph{
    int n; //nr de noduri
    int m; //nr de muchii
    vector <vector <int> > edges; //vector ce contine cate un vector cu vecini pt fiecare nod
    bool oriented; // variabiabila pt a verifca daca e orientat
    bool from1; // variabila pt a verifica daca nodurile sunt numerotate de la 1
public:
    //constructori:
    Graph(int, bool, bool);
    Graph(int, int, bool, bool);

    void insert_edge(int, int); //functie pt a insera muchii
    vector <int> bfs (int); //functie pt a afla distantele minime de la un nod la celelate

};
Graph::Graph (int n, bool oriented , bool from1){
    this->n = n;
    m = 0;
    this->from1 = from1;
    this-> oriented = oriented;
    for(int i = 0; i < n; i++){
        vector <int> aux;
        edges.push_back(aux);
    }
}
Graph::Graph (int n, int m, bool oriented , bool from1){
    this->n = n;
    this->m = m;
    this->from1 = from1;
    this-> oriented = oriented;
    for(int i = 0; i < n; i++){
        vector <int> aux;
        edges.push_back(aux);
    }
}

void Graph::insert_edge (int x, int y){
    if(from1){
        edges[x-1].push_back(y-1);
        if(!oriented)
            edges[y-1].push_back(x-1);
    }
    else{
        edges[x].push_back(y);
        if(!oriented)
            edges[y].push_back(x);
    }
}

vector <int> Graph::bfs(int x){
    vector <int> dist; //vector pt a memora distantele
    queue <int> aux; //coada ce retine nodurile ce trebuie explorate
    for(int i = 0; i < n; i++)
        //nodurile nevizitate primesc distanta -1:
        dist.push_back(-1); 
    if(from1)
        x--;
    aux.push(x);
    dist[x] = 0;
    while(!aux.empty()){
        for(int i = 0; i < edges[ aux.front() ].size() ;i++){
            //verificam daca nodurile vecine cu cel din varful cozii nu au fost vizitate:
            if(dist[ edges[aux.front()][i] ] == -1){
                //retinem distanta:
                dist[ edges[aux.front()][i] ] = dist[ aux.front() ] + 1; 
                //adaugam nodul vizitat in coada:
                aux.push( edges[aux.front()][i] );
            }
        }
        //trecem la urmatorul nod ce trebuie explorat:
        aux.pop();
    }
    return dist;
}


int main(){
    int n,m,x,a,b;
    fin>>n>>m>>x;
    Graph v (n,m,true,true);
    for(int i =0; i<m;i++){
        fin>>a>>b;
        v.insert_edge(a,b);

    }
    vector<int> aux;
    aux=v.bfs(x);
    for(int i=0;i<aux.size();i++)
        fout<<aux[i]<<" ";
   
}