#include <bits/stdc++.h>
int head[500001], nxt[1000001], b[1000001], k = 1, n, m, stk[500010], top, cnt,
                                            dfn[500010], low[500010], now,
                                            V[500010], pre[500010];
int f[1000001], oth[1000001], edg[1000001][2], g[1000001];
std::vector<std::pair<int, int> > con[1000001];
void push(int s, int t) {
  nxt[++k] = head[s];
  head[s] = k;
  b[k] = t;
}
void tarjan(int x, int f) {
  stk[++top] = x;
  V[top] = f;
  low[x] = dfn[x] = ++now;
  for (int i = head[x]; i; i = nxt[i])
    if ((i >> 1) != (f >> 1)) {
      if (!dfn[b[i]]) {
        tarjan(b[i], i);
        low[x] = std::min(low[x], low[b[i]]);
        if (low[b[i]] > dfn[x]) {
          ++cnt;
          con[x].push_back(std::make_pair(b[i], i)), --top;
        }
        if (low[b[i]] == dfn[x]) {
          ++cnt;
          con[x].push_back(std::make_pair(cnt, pre[stk[top]]));
          con[cnt].push_back(std::make_pair(x, pre[stk[top]]));
          while (stk[top + 1] != b[i]) {
            con[cnt].push_back(std::make_pair(stk[top], V[top]));
            --top;
          }
        }
      } else {
        low[x] = std::min(low[x], dfn[b[i]]);
        if (dfn[b[i]] < dfn[x]) pre[x] = i;
      }
    }
}
void solve(int x) {
  if (x <= n) {
    for (int i = 0; i < con[x].size(); i++) solve(con[x][i].first);
  } else {
    int mn = 0, mx = 0;
    for (int i = 1; i < con[x].size(); i++) {
      if (con[x][mn].second > con[x][i].second) mn = i;
      if (con[x][mx].second < con[x][i].second) mx = i;
      solve(con[x][i].first);
    }
    int stat = 0;
    for (int i = mx;;) {
      int nxt = (i == con[x].size() - 1) ? 0 : (i + 1);
      if (con[x][nxt].second > con[x][i].second) break;
      i = nxt;
      if (i == mn) {
        stat |= 1;
        break;
      }
    }
    for (int i = mx;;) {
      int nxt = (i ? i : con[x].size()) - 1;
      if (con[x][nxt].second > con[x][i].second) break;
      i = nxt;
      if (i == mn) {
        stat |= 2;
        break;
      }
    }
    if (stat == 3) oth[con[x][mn].second >> 1] = con[x][mx].second >> 1;
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) f[i] = 1;
  for (int i = 1, u, v; i <= m; i++)
    scanf("%d%d", &u, &v), push(u, v), push(v, u), edg[i][0] = u, edg[i][1] = v;
  cnt = n;
  tarjan(1, 0);
  solve(1);
  for (int i = m; i; i--)
    g[i] = f[edg[i][0]] = (f[edg[i][1]] += f[edg[i][0]] - g[oth[i]]);
  for (int i = 1; i <= n; i++) printf("%d ", f[i] - 1);
}

### 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>
int head[500001], nxt[1000001], b[1000001], k = 1, n, m, stk[500010], top, cnt,
                                            dfn[500010], low[500010], now,
                                            V[500010], pre[500010];
int f[1000001], oth[1000001], edg[1000001][2], g[1000001];
std::vector<std::pair<int, int> > con[1000001];
void push(int s, int t) {
  nxt[++k] = head[s];
  head[s] = k;
  b[k] = t;
}
void tarjan(int x, int f) {
  stk[++top] = x;
  V[top] = f;
  low[x] = dfn[x] = ++now;
  for (int i = head[x]; i; i = nxt[i])
    if ((i >> 1) != (f >> 1)) {
      if (!dfn[b[i]]) {
        tarjan(b[i], i);
        low[x] = std::min(low[x], low[b[i]]);
        if (low[b[i]] > dfn[x]) {
          ++cnt;
          con[x].push_back(std::make_pair(b[i], i)), --top;
        }
        if (low[b[i]] == dfn[x]) {
          ++cnt;
          con[x].push_back(std::make_pair(cnt, pre[stk[top]]));
          con[cnt].push_back(std::make_pair(x, pre[stk[top]]));
          while (stk[top + 1] != b[i]) {
            con[cnt].push_back(std::make_pair(stk[top], V[top]));
            --top;
          }
        }
      } else {
        low[x] = std::min(low[x], dfn[b[i]]);
        if (dfn[b[i]] < dfn[x]) pre[x] = i;
      }
    }
}
void solve(int x) {
  if (x <= n) {
    for (int i = 0; i < con[x].size(); i++) solve(con[x][i].first);
  } else {
    int mn = 0, mx = 0;
    for (int i = 1; i < con[x].size(); i++) {
      if (con[x][mn].second > con[x][i].second) mn = i;
      if (con[x][mx].second < con[x][i].second) mx = i;
      solve(con[x][i].first);
    }
    int stat = 0;
    for (int i = mx;;) {
      int nxt = (i == con[x].size() - 1) ? 0 : (i + 1);
      if (con[x][nxt].second > con[x][i].second) break;
      i = nxt;
      if (i == mn) {
        stat |= 1;
        break;
      }
    }
    for (int i = mx;;) {
      int nxt = (i ? i : con[x].size()) - 1;
      if (con[x][nxt].second > con[x][i].second) break;
      i = nxt;
      if (i == mn) {
        stat |= 2;
        break;
      }
    }
    if (stat == 3) oth[con[x][mn].second >> 1] = con[x][mx].second >> 1;
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) f[i] = 1;
  for (int i = 1, u, v; i <= m; i++)
    scanf("%d%d", &u, &v), push(u, v), push(v, u), edg[i][0] = u, edg[i][1] = v;
  cnt = n;
  tarjan(1, 0);
  solve(1);
  for (int i = m; i; i--)
    g[i] = f[edg[i][0]] = (f[edg[i][1]] += f[edg[i][0]] - g[oth[i]]);
  for (int i = 1; i <= n; i++) printf("%d ", f[i] - 1);
}

```