#include <stdio.h>

#define MAX_M 3000
#define MAX_N 3000

typedef struct {
  int v, next;
} list;

int N, M;
int adj[MAX_N + 1];
list l[MAX_M * 2 + 1];
char seen[MAX_N + 1];
int d[MAX_N + 1][MAX_N + 1];

void dfs(int u) {
  int pos, v, i, j;
  seen[u] = 1;
  int count = 0;
  fprintf(stderr, "Sune la %d\n", u);
  for (pos = adj[u]; pos; pos = l[pos].next) {
    v = l[pos].v;
    if (!seen[v]) {
      count++;
      dfs(v);
      if (count == 1) {
        for (i = 1; i <= N; i++) {
          d[u][i] = d[v][i] + 1;
        }
      } else {
        fprintf(stderr, "Vewcin ; %d cu %d\n", u, v);
      for (j = 1; j <= N; j++) {
        for (i = N; i >= 0; i--) {
                      if (u == 4 && i + j <= N)
            fprintf(stderr, "Fac pentru %d -> %d in %d\n ", j + i, d[v][j] + d[u][i] + 1, d[u][i + j]);
          if (i + j <= N && (d[u][j + i] == 0 || d[v][j] + d[u][i] + 1 > d[u][j + i])) {
            if (u == 4)
            fprintf(stderr, "Fac pentru %d -> %d\n ", j + i, d[v][j] + d[u][i] + 1);
            d[u][j + i] = d[v][j] + d[u][i] + 1;
          }
        }
      }
      }
    }
  }
  //fprintf(stderr, "a iesit cu %d\n", count);
  for (i = N; i >= 1; i--) {
    d[u][i] = d[u][i - 1];
  }

  if (u == 4) {
  fprintf(stderr, "Pentru nodu %d: \n", u);
  for (i = 1; i <= N; i++) {
    fprintf(stderr, "%d ", d[u][i]);
  }
  }
  fprintf(stderr, "\n");
//d[u][1] = ;
}

int buff;

void addEdge(int u, int v) {
  buff++;
  l[buff].v = v;
  l[buff].next = adj[u];
  adj[u] = buff;
}

int main(void) {
  int u, i ,v;
  FILE *f = fopen("1.in", "r");

  fscanf(f, "%d %d", &N, &M);
  for (i = 1; i <= M; i++) {
    fscanf(f, "%d %d", &u, &v);
    addEdge(u, v);
    addEdge(v, u);
  }
  fclose(f);

  dfs(1);

      fprintf(stderr, "amin");

  for (u = 1; u <= N; u++) {
    fprintf(stderr, "Nodul %d: ", u);
    for (i = 1; i <= N; i++) {
      fprintf(stderr, "%d ", d[u][i]);
    }
    fprintf(stderr, "\n");
  }

  //freopen("1.out", "w", stdout);
  fclose(stdout);
  return 0;
}