Problem: You are given a special connected undirected graph where each vertex belongs to at most one simple cycle.

Your task is to remove as many edges as needed to convert this graph into a tree (connected graph with no cycles). 

For each node, independently, output the maximum distance between it and a leaf in the resulting tree, assuming you were to remove the edges in a way that minimizes this distance.

Input

The first line of input contains two integers n and m (1 ≤ n ≤ 5⋅ 10^5), the number of nodes and the number of edges, respectively.

Each of the following m lines contains two integers u and v (1 ≤ u,v ≤ n, u ≠ v), and represents an edge connecting the two nodes u and v. Each pair of nodes is connected by at most one edge.

It is guaranteed that the given graph is connected and each vertex belongs to at most one simple cycle.

Output

Print n space-separated integers, the i-th integer represents the maximum distance between node i and a leaf if the removed edges were chosen in a way that minimizes this distance.

Examples

Input

9 10
7 2
9 2
1 6
3 1
4 3
4 7
7 6
9 8
5 8
5 9


Output

5 3 5 4 5 4 3 5 4


Input

4 4
1 2
2 3
3 4
4 1


Output

2 2 2 2

Note

In the first sample, a possible way to minimize the maximum distance from vertex 1 is by removing the marked edges in the following image:

<image>

Note that to minimize the answer for different nodes, you can remove different edges.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;
ostream &operator<<(ostream &o, ii p) {
  return o << "(" << p.first << ", " << p.second << ")";
}
static const int MAX = 500100;
static vi cycle_nodes[MAX];
static int cycle_of[MAX];
static vi c_nbors[MAX];
static int pos_in_cycle[MAX];
static int N, cN;
static vi nbors[MAX];
struct Edge {
  int u, v, dp;
  bool is_solved;
  Edge *reverse;
  bool is_on_cycle() { return cycle_of[u] == cycle_of[v]; }
};
static vector<Edge> edges[MAX];
static bool seen[MAX];
static bool taken[MAX];
static int trpos[MAX];
static void add_cycle(int *l, int *r) {
  int id = ++cN;
  ((void)0);
  int pos = 0;
  for (int *it = l; it != r; it++) {
    ((void)0);
    cycle_nodes[id].push_back(*it);
    taken[*it] = true;
    cycle_of[*it] = id;
    pos_in_cycle[*it] = pos++;
  }
}
static void find_cycles(int u, int p) {
  static vi trace;
  if (seen[u]) {
    int l = trpos[u];
    int r = trace.size();
    add_cycle(&trace[l], &trace[r]);
  } else {
    trpos[u] = trace.size();
    trace.push_back(u);
    seen[u] = true;
    for (int v : nbors[u])
      if (v != p && !taken[v]) find_cycles(v, u);
    if (!taken[u]) {
      add_cycle(&trace[trpos[u]], &trace[trpos[u] + 1]);
    }
    trace.pop_back();
  }
}
static void connect_cycles() {
  for (auto id = (1); id < (cN + 1); id++) {
    for (int u : cycle_nodes[id]) {
      for (int v : nbors[u])
        if (cycle_of[v] != id) {
          ((void)0);
          c_nbors[id].push_back(cycle_of[v]);
        }
    }
  }
}
static Edge *that_edge[MAX];
static int dist(int u, int v) {
  assert(cycle_of[u] == cycle_of[v]);
  int m = cycle_nodes[cycle_of[u]].size();
  int d1 = (pos_in_cycle[u] - pos_in_cycle[v] + m) % m;
  int d2 = (pos_in_cycle[v] - pos_in_cycle[u] + m) % m;
  int d = min(d1, d2);
  ((void)0);
  return d;
}
static int qdata[MAX * 2];
static int ql, qr;
static void q_reset() {
  ql = qr = 0;
  ((void)0);
}
static pair<int, int> q_top() {
  assert(ql < qr);
  ii r;
  if (ql + 1 < qr)
    r = {qdata[ql], qdata[ql + 1]};
  else
    r = {qdata[ql], -MAX};
  ((void)0);
  return r;
}
static void q_pop(int x) {
  if (ql < qr && qdata[ql] == x) {
    ql++;
  }
}
static void q_push(int x) {
  while (ql < qr && qdata[qr - 1] < x) {
    qr--;
  }
  qdata[qr++] = x;
}
static void q_pop(ii x) {
  ((void)0);
  q_pop(x.first);
  q_pop(x.second);
}
static void q_push(ii x) {
  ((void)0);
  q_push(x.first);
  q_push(x.second);
}
static void add(pair<int, int> &h, int g) {
  if (h.first <= g) {
    h.second = h.first;
    h.first = g;
  } else if (h.second < g)
    h.second = g;
}
static void add(pair<int, int> &h, pair<int, int> g) {
  add(h, g.first);
  add(h, g.second);
}
static ii operator-(ii x, int y) { return {x.first - y, x.second - y}; }
static ii operator+(ii x, int y) { return {x.first + y, x.second + y}; }
static int get_best(ii heap, int x) {
  if (heap.first == x)
    return heap.second;
  else
    return heap.first;
}
static int ans[MAX];
static bool is_finalized[MAX];
static void finalize(int id) {
  if (is_finalized[id]) return;
  is_finalized[id] = true;
  ((void)0);
  static ii buf[MAX * 2];
  static ii tmp[MAX];
  int n = cycle_nodes[id].size();
  for (auto i = (0); i < (n); i++) {
    int u = cycle_nodes[id][i];
    ii x = {0, -MAX};
    for (Edge &out : edges[u])
      if (!out.is_on_cycle()) {
        assert(out.is_solved);
        add(x, out.dp + 1);
      }
    buf[i] = x;
    ((void)0);
  }
  copy(buf, buf + n, buf + n);
  int f = (n + 1) / 2;
  int b = n / 2;
  for (auto i = (0); i < (n); i++) tmp[i] = {0, 0};
  q_reset();
  for (auto i = (0); i < (f); i++) q_push(buf[i] + i);
  for (auto i = (0); i < (n); i++) {
    add(tmp[i], q_top() - i);
    ((void)0);
    q_pop(buf[i] + i);
    q_push(buf[i + f] + f + i);
  }
  if (n > 1) {
    q_reset();
    for (int i = b - 1; i >= 0; i--) q_push(buf[n - i - 1] + i + 1);
    for (auto i = (0); i < (n); i++) {
      add(tmp[i], q_top() + i);
      ((void)0);
      q_pop(buf[n - b + i] - i + b);
      q_push(buf[n + i] - i);
    }
  }
  for (auto i = (0); i < (n); i++) {
    int u = cycle_nodes[id][i];
    ans[u] = tmp[i].first;
    ((void)0);
    for (Edge &out : edges[u])
      if (!out.is_on_cycle()) {
        Edge &in = *out.reverse;
        in.is_solved = true;
        assert(in.v == u);
        in.dp = get_best(tmp[i], out.dp + 1);
        ((void)0);
      }
  }
}
static void solve(Edge &e) {
  if (e.is_solved) return;
  ((void)0);
  int id = cycle_of[e.v];
  if (that_edge[id]) {
    assert(&e != that_edge[id]);
    solve(*that_edge[id]);
    finalize(id);
  } else {
    that_edge[id] = e.reverse;
    int ans = 0;
    for (int u : cycle_nodes[id]) {
      ans = max(ans, dist(e.v, u));
      for (Edge &out : edges[u])
        if (!out.is_on_cycle() && out.v != e.u) {
          solve(out);
          ans = max(ans, dist(e.v, out.u) + 1 + out.dp);
        }
    }
    e.dp = ans;
    e.is_solved = true;
    ((void)0);
  }
}
int main() {
  int m;
  cin >> N >> m;
  ii *mem = new ii[m];
  for (auto i = (0); i < (m); i++) {
    int u, v;
    cin >> u >> v;
    mem[i] = {u, v};
    nbors[u].push_back(v);
    nbors[v].push_back(u);
    edges[u].push_back({u, v, -1, false, nullptr});
    edges[v].push_back({v, u, -1, false, nullptr});
  }
  static int deg[MAX];
  for (auto i = (0); i < (m); i++) {
    int u = mem[i].first;
    int v = mem[i].second;
    edges[u][deg[u]].reverse = &edges[v][deg[v]];
    edges[v][deg[v]].reverse = &edges[u][deg[u]];
    deg[u]++;
    deg[v]++;
  }
  find_cycles(1, 1);
  connect_cycles();
  for (auto i = (1); i < (N + 1); i++) {
    for (auto &e : edges[i])
      if (!e.is_on_cycle()) {
        solve(e);
      }
  }
  for (auto id = (1); id < (cN + 1); id++) {
    finalize(id);
  }
  for (auto i = (1); i < (N + 1); i++) {
    printf("%i%c", ans[i], " \n"[i == N]);
  }
  return 0;
}