#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
ifstream in("data.in");
ofstream out("data.out");
using namespace std;

class Graph {
    int nr_muchii, nr_noduri, nod_start;
    vector<vector<pair<int, int>>> lista_vecini;
    void BFS (unsigned int nod_start, int[]);
public:
    Graph(string, bool);
    void problemaBFS();

};

Graph::Graph(string optiune, bool are_nod_start = false) {
    if (optiune == "orientat") {
        in >> this->nr_noduri >> this->nr_muchii;
        this->lista_vecini.resize(this->nr_noduri + 1);
        if (are_nod_start) {
            in >> this->nod_start;
        }

        int muchie_a, muchie_b;
        for (unsigned int i = 1; i <= this->nr_muchii; i ++) {
            in >> muchie_a >> muchie_b;
            cout << muchie_a << " " << muchie_b << endl;
            this->lista_vecini[muchie_a].push_back(make_pair(muchie_b, 0));
        }
    }

//    cout << endl;
//    for (int i = 0; i < this->lista_vecini.size(); i ++) {
//        cout << i << ": ";
//        for (int j = 0; j < this->lista_vecini[i].size(); j++) {
//            cout << "(" << this->lista_vecini[i][j].first << "," << this->lista_vecini[i][j].second << "), ";
//        }
//        cout << endl;
//    }

    if (optiune == "neorientat") {
        int noduri, muchii;
        in >> noduri >> muchii;
        this->nr_noduri = noduri;
        this->nr_muchii = muchii;

        if (are_nod_start) {
            int nod_start;
            in >> nod_start;
            this->nod_start = nod_start;
        }

        int muchie_a, muchie_b;
        for (unsigned int i = 1; i <= nr_muchii; i ++) {
            in >> muchie_a >> muchie_b;
            this->lista_vecini[muchie_a].push_back(make_pair(muchie_b, 0));
            this->lista_vecini[muchie_b].push_back(make_pair(muchie_a, 0));
        }
    }
}

void Graph::BFS (unsigned int nod_start, int vizitat[]) {
    unsigned int index = 0;
    vector <int> coada;
    coada.push_back(nod_start);
    vizitat[nod_start] = 0;
    while (index < coada.size()) {
        int nod_curent = coada[index ++];
        for (unsigned int i = 0; i < this->lista_vecini[nod_curent].size(); ++i) {
            if (vizitat[this->lista_vecini[nod_curent][i].first] == -1) {
                coada.push_back(this->lista_vecini[nod_curent][i].first);
                vizitat[this->lista_vecini[nod_curent][i].first] = vizitat[nod_curent] + 1;
            }
        }
    }
};

void Graph::problemaBFS () {
    int vizitat[nr_noduri + 1];
    for (unsigned int i = 1; i <= nr_noduri; i ++) {
        vizitat[i] = -1;
    }
    BFS(nod_start, vizitat);
    for (unsigned int i = 1; i <= nr_noduri; i++) {
        cout << vizitat[i] << " ";
    }
}

int main() {
    string problema;
    cin >> problema;
//    if (problema == "bfs") {
        in.open ("bfs.in", fstream::in);
        out.open ("bfs.out", fstream::out);
        Graph graf("orientat", true);
        graf.problemaBFS();
//    }

}