#include<iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#include <queue>

using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
class GrafMatrix;
class Graf{
private:
    unordered_map<int,vector<int>> nod;
    int n;
    void dfs(int start, unordered_set<int> &v){
        if(v.find(start)!=v.end())
            return;
        v.insert(start);
        fout<<start<<" ";
        for(int vec:nod[start])
            if(v.find(vec)==v.end())
                dfs(vec,v);
    }
    void add_neorientat(int st,int dr){
        if(nod.find(st)==nod.end())
            nod[st]=vector<int>();
        if(nod.find(dr)==nod.end())
            nod[dr]=vector<int>();
        nod[st].push_back(dr);
        nod[dr].push_back(st);
    }
    void add_orientat(int st, int dr){
        if(nod.find(st)==nod.end())
            nod[st]=vector<int>();
        nod[st].push_back(dr);
    }
public:
    Graf(int n){this->n=n;}
    Graf(){};
    void add(int o){
        int a,b;
        fin>>a>>b;
        if(o)
            add_orientat(a,b);
        else
            add_neorientat(a,b);
    }
    void dfs(int start){
        unordered_set<int> v;
        dfs(start,v);
    }
    void afis(){
        for(int i=1;i<=n;i++){
            fout<<i<<") ";
                for(auto k:nod[i])
                    fout<<k<<" ";
            fout<<"\n";
        }
    }
    vector<int> bfs(int start){
        unordered_set<int> v;
        queue<int> q;
        vector<int> rez;
        for(int i=0;i<n;i++)
            rez.push_back(-1);
        rez[start-1]=0;

        v.insert(start);
        q.push(start);
        while(!q.empty()){
            int nod_cur=q.front();
            q.pop();

            for(int vec:nod[nod_cur])
                if(v.find(vec)==v.end()){
                    q.push(vec);
                    v.insert(vec);
                    rez[vec-1]=rez[nod_cur-1]+1;
                }
        }
        return rez;
    }
};

class GrafMatrix{
    vector<vector<int>> mat_ad;
    int n;
    void add_neorientat(){
        int a,b;
        fin>>a>>b;
        mat_ad[a][b]=1;
        mat_ad[b][a]=1;
    }
    void add_orientat(){
        int a,b;
        fin>>a>>b;
        mat_ad[a][b]=1;
    }
public:
    GrafMatrix(int n){
        this->n=n;
        mat_ad.resize(n+1,vector<int>(n+1));
    }
    void add(int orientat){
        if(orientat==0)
            add_neorientat();
        else
            add_orientat();

    }
    void afis(){
        for(int i=1;i<=n;i++){
            fout<<i<<") ";
            for(int j=1;j<=n;j++)
                if(mat_ad[i][j]==1)
                    fout<<j<<" ";
            fout<<"\n";
        }
    }
    void printMatrix(){
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
                fout<<mat_ad[i][j]<<" ";
            fout<<"\n";
        }
    }
};
int main()
{
    int n,m,o=1,start;
    fin>>n>>m>>start;
    Graf g(n);
    for(int i=1;i<=m;i++)
        g.add(o);
    vector<int> rez=g.bfs(start);
    for(auto x:rez)
        fout<<x<<" ";
    return 0;
}