#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;
///ifstream f ("dfs.in");ofstream g ("dfs.out");
ifstream f("bfs.in");ofstream g("bfs.out");
vector<int> distanta(100001, -1);
class graf{
private:
    int n, m, x, y, counter=0;
    int verif [100001];
    queue <int> coada;
    vector <int> muchii[100001];
public:
    graf(){}
    graf (int n, int m)  ///constructor graf neorientat
    {
        this-> n = n;
        this-> m = m;

        for(int i=1; i<=m; i++){
            f>>x>>y;
            muchii[x].push_back(y);
            muchii[y].push_back(x);
        }
    }
    graf (int n, int m, int o){ /// constructor graf orientat
        this-> n = n;
        this-> m = m;

        for(int i=1;i<=m;i++){
            f>>x>>y;
            muchii[x].push_back(y);
        }
    }
    void dfs(int nod){    /// dfs simplu
        verif[nod]=true;
        for (int i=0; i<muchii[nod].size(); i++){
            int vecin = muchii[nod][i];
            if(verif[vecin]!=true)
                dfs(vecin);
        }
    }
    void bfs()   /// bfs simplu
    {
        int nod, vecin;
        while(!coada.empty())
        {
            nod=coada.front();
            coada.pop();
            for (int i= 0;i<muchii[nod].size();i++)
            {
                vecin = muchii[nod][i];
                if(distanta[vecin]==-1)
                {
                    coada.push(vecin);
                    distanta[vecin]=distanta[nod]+1;
                }
            }
        }
    }

    void dfsRez(){    /// rezolvare problema dfs
        for (int i=1;i<=n;i++){
            if (verif[i]!=true){
                counter++;
                dfs(i);
            }
        }
        g<<counter;
        }
    void bfsRez(){
        int nods;
        f>>nods;
        distanta[nods]=0;

        coada.push(nods);
        bfs();
        for (int i=1;i<=n;i++){
            g<<distanta[i] <<" ";
        }

    }
virtual ~graf(){}
};
int main()
{
    /// int n, m;f>>n>>m;graf g1(n,m);g1.dfsRez();     ///dfs 100p
    int n,m; f>>n>>m; graf g1(n,m,0); g1.bfsRez();
    return 0;
}