#include <bits/stdc++.h>

using namespace std;

ifstream f("bfs.in");
ofstream g("bfs.out");

class graf
{
    int nr_noduri, nr_muchii;

    vector<vector<int> > lista_muchii;

    bool orientat;

public:
    graf();

    graf(int nr_noduri, int nr_muchii, bool orientat);

    ~graf() {}

    void BFS(int start);
};

graf::graf()
{
    nr_noduri = 0;
    nr_muchii = 0;
    orientat = 0;
}

graf::graf(int nr_noduri, int nr_muchii, bool orientat)
{
    int i = 0, nod1, nod2;

    lista_muchii.resize(nr_noduri+1);

    this->nr_noduri = nr_noduri;
    this->nr_muchii = nr_muchii;
    this->orientat = orientat;

    while(i < nr_muchii)
    {
        f>>nod1>>nod2;
        if(orientat)
            lista_muchii[nod1].push_back(nod2);
        else
        {
            lista_muchii[nod1].push_back(nod2);
            lista_muchii[nod2].push_back(nod1);
        }
        i++;
    }
}

void graf::BFS(int inceput)
{
    int i = 0, nod_curent;

    queue<int> q;

    vector<bool>vizitat;
    vector<int>distanta;

    do
    {
        vizitat.push_back(0);
        distanta.push_back(-1);
        i++;

    }while(i <= nr_noduri);

    q.push(inceput);

    vizitat[inceput] = 1;
    distanta[inceput] = 0;

    while(!q.empty())
        {
            nod_curent = q.front();
            q.pop();
            for (auto j = lista_muchii[nod_curent].begin(); j != lista_muchii[nod_curent].end(); j++)
                if(!vizitat[*j])
                {
                    vizitat[*j] = 1;
                    q.push(*j);
                    distanta[*j] = distanta[nod_curent] + 1;
                }
        }
    int marime = distanta.size();
    for(i = 1; i < marime; i++)
        g<<distanta[i]<<" ";
}

int main()
{
    int n, m, s;
    f>>n>>m>>s;

    graf test(n,m,1);

    test.BFS(s);
    return 0;
}