#include <stdio.h>
#include <stdlib.h>

typedef struct tfila{
  int dados[100];
  int p, u;
}fila;

fila* criarfila(){
  fila* F = (fila*) malloc(sizeof(fila));
  F->u = 0;
  F->p = 0;
  return F;
}

void colocarnafila(fila* F, int x){
  F->dados[F->u] = x;
  F->u = F->u + 1;
  if(F->u == 100) F->u = 0;
  return;
}

int retirardafila(fila* F){
  int primeiro = F->dados[F->p];
  F->dados[F->p] = -1;
  F->p++;
  if(F->p == 100) F->p = 0;
  return primeiro;
}

int filavazia(fila* F){
  if(F->p == F->u) return 1;
  else return 0;
}

int filacheia(fila* F){
  if(F->p == F->u + 1 || (F->p == 0 && F->u == 99)) return 1;
  else return 0;
}

void distancias(int ** M, int n){
  int * dist = (int*) malloc(n * sizeof(int));
  //Nao conheco caminho para nenhuma cidade
  for(int i = 0; i < n; i++){
    dist[i] = n;
  }
  dist[0] = 0;

  fila * F = criarfila();
  colocarnafila(F, 0);

  while(!filavazia(F)){
    int i = retirardafila(F);
    for(int j = 0; j < n; j++){
      if(M[i][j] == 1 && dist[j] == n){
        colocarnafila(F, j);
        dist[j] = dist[i] + 1;
      }
    }
  }
  for(int i = 0; i < n; i++){
    printf("%d: %d hs\n", i, dist[i]);
  }
  printf("\n");
}

int main(int argc, char* argv[]){
  int ** M;
  int n;
  scanf("%d", &n);
  M = (int**) malloc(n * sizeof(int*));
  for(int i = 0; i < n; i++){
    M[i] = (int*) malloc(n * sizeof(int));
  }

  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      scanf("%d", &(M[i][j]));
    }
  }
  distancias(M, n);

  return 0;
}