#include <deque>
#include <iostream>
#include <vector>

int main( ) {
   int n, m;
   std::cin >> n >> m;

   std::vector<std::vector<int>> listas(n);
   for (int i = 0; i < m; ++i) {
      int v1, v2;
      std::cin >> v1 >> v2;
      listas[v1].push_back(v2);
      listas[v2].push_back(v1);
   }

   std::deque<int> cola = { 0 };
   std::vector<int> distancia(n, -1);
   distancia[0] = 0;
   do {
      int procesar = cola.front( );
      cola.pop_front( );
      for (int v : listas[procesar]) {
         if (distancia[v] == -1) {
            distancia[v] = distancia[procesar] + 1;
            cola.push_back(v);
         }
      }
   } while (!cola.empty( ));

   for (int i = 0; i < n; ++i) {
      std::cout << i << ": " << distancia[i] << "\n";
   }
}