#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  if (flag) x = -x;
}
int n, m, cnt, tot;
int f[1000010], g[1000010], bel[1000010], fa[1000010], pre[1000010],
    dfn[1000010], nxt[1000010], t[1000010];
struct edge {
  int to, nxt, id;
} e[1000010];
int head[1000010], edge_cnt;
void add(int from, int to, int id) {
  e[++edge_cnt] = {to, head[from], id}, head[from] = edge_cnt;
}
struct node {
  int x, y;
} p[1000010];
bool check(int pmx, int pmn) {
  int x = pmx;
  while (x != pmn) {
    if (t[x] < t[nxt[x]]) return false;
    x = nxt[x];
  }
  while (x != pmx) {
    if (t[x] > t[nxt[x]]) return false;
    x = nxt[x];
  }
  return true;
}
void dfs(int x, int fath) {
  dfn[x] = ++cnt, fa[x] = fath;
  for (int i = head[x]; i; i = e[i].nxt) {
    int y = e[i].to;
    if (dfn[y]) continue;
    pre[y] = e[i].id, dfs(y, x);
  }
  for (int i = head[x]; i; i = e[i].nxt) {
    int y = e[i].to, pmx, mx = -1000000000, pmn, mn = 1000000000;
    if (y == fath || x == fa[y] || dfn[y] <= dfn[x]) continue;
    t[tot = 1] = e[i].id;
    while (x != y) t[++tot] = pre[y], y = fa[y];
    for (int j = 1; j <= tot; ++j) {
      nxt[j] = j + 1;
      if (t[j] > mx) mx = t[j], pmx = j;
      if (t[j] < mn) mn = t[j], pmn = j;
    }
    nxt[tot] = 1;
    if (check(pmx, pmn)) bel[t[pmx]] = t[pmn];
  }
}
int main() {
  read(n), read(m);
  for (int i = 1; i <= m; ++i) {
    int x, y;
    read(x), read(y);
    add(x, y, i), add(y, x, i), p[i] = {x, y};
  }
  dfs(1, 0);
  for (int i = 1; i <= n; ++i) f[i] = 1;
  for (int i = m; i; --i) {
    int x = p[i].x, y = p[i].y, v = f[x] + f[y] - g[i];
    g[bel[i]] = f[x] = f[y] = v;
  }
  for (int i = 1; i <= n; ++i) printf("%d ", f[i] - 1);
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

You are given a cactus graph, in this graph each edge lies on at most one simple cycle.

It is given as m edges a_i, b_i, weight of i-th edge is i.

Let's call a path in cactus increasing if the weights of edges on this path are increasing.

Let's call a pair of vertices (u,v) happy if there exists an increasing path that starts in u and ends in v.

For each vertex u find the number of other vertices v, such that pair (u,v) is happy.

Input

The first line of input contains two integers n,m (1 ≤ n, m ≤ 500 000): the number of vertices and edges in the given cactus.

The next m lines contain a description of cactus edges, i-th of them contain two integers a_i, b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i).

It is guaranteed that there are no multiple edges and the graph is connected.

Output

Print n integers, required values for vertices 1,2,…,n.

Examples

Input


3 3
1 2
2 3
3 1


Output


2 2 2 


Input


5 4
1 2
2 3
3 4
4 5


Output


4 4 3 2 1 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  if (flag) x = -x;
}
int n, m, cnt, tot;
int f[1000010], g[1000010], bel[1000010], fa[1000010], pre[1000010],
    dfn[1000010], nxt[1000010], t[1000010];
struct edge {
  int to, nxt, id;
} e[1000010];
int head[1000010], edge_cnt;
void add(int from, int to, int id) {
  e[++edge_cnt] = {to, head[from], id}, head[from] = edge_cnt;
}
struct node {
  int x, y;
} p[1000010];
bool check(int pmx, int pmn) {
  int x = pmx;
  while (x != pmn) {
    if (t[x] < t[nxt[x]]) return false;
    x = nxt[x];
  }
  while (x != pmx) {
    if (t[x] > t[nxt[x]]) return false;
    x = nxt[x];
  }
  return true;
}
void dfs(int x, int fath) {
  dfn[x] = ++cnt, fa[x] = fath;
  for (int i = head[x]; i; i = e[i].nxt) {
    int y = e[i].to;
    if (dfn[y]) continue;
    pre[y] = e[i].id, dfs(y, x);
  }
  for (int i = head[x]; i; i = e[i].nxt) {
    int y = e[i].to, pmx, mx = -1000000000, pmn, mn = 1000000000;
    if (y == fath || x == fa[y] || dfn[y] <= dfn[x]) continue;
    t[tot = 1] = e[i].id;
    while (x != y) t[++tot] = pre[y], y = fa[y];
    for (int j = 1; j <= tot; ++j) {
      nxt[j] = j + 1;
      if (t[j] > mx) mx = t[j], pmx = j;
      if (t[j] < mn) mn = t[j], pmn = j;
    }
    nxt[tot] = 1;
    if (check(pmx, pmn)) bel[t[pmx]] = t[pmn];
  }
}
int main() {
  read(n), read(m);
  for (int i = 1; i <= m; ++i) {
    int x, y;
    read(x), read(y);
    add(x, y, i), add(y, x, i), p[i] = {x, y};
  }
  dfs(1, 0);
  for (int i = 1; i <= n; ++i) f[i] = 1;
  for (int i = m; i; --i) {
    int x = p[i].x, y = p[i].y, v = f[x] + f[y] - g[i];
    g[bel[i]] = f[x] = f[y] = v;
  }
  for (int i = 1; i <= n; ++i) printf("%d ", f[i] - 1);
  return 0;
}

```