#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
map<int, int> f[N];
bool fl[N], fq[N];
long long f1[N], f2[N], dp1[N];
int n, m, k, q, c[N], g1[N], qt[N], st[N], low[N], dfn[N], cnt[N], sum[N];
vector<int> v[N], w[N], z[N];
struct edge {
  int u, t, w;
} e[N];
inline int read() {
  int num = 0;
  char g = getchar();
  while (g < 48 || 57 < g) g = getchar();
  while (47 < g && g < 58)
    num = (num << 1) + (num << 3) + g - 48, g = getchar();
  return num;
}
inline void tarjan(int u, int fa) {
  st[++st[0]] = u, low[u] = dfn[u] = ++k;
  int c = st[0];
  for (int i = 0; i < v[u].size(); i++) {
    int x = v[u][i];
    if (x == fa) continue;
    if (!dfn[x]) {
      tarjan(x, u), low[u] = min(low[u], low[x]);
      if (low[x] >= dfn[u]) {
        q++;
        while (st[st[0] + 1] != x) z[q].push_back(st[st[0]]), st[0]--;
        z[q].push_back(u);
        if (z[q].size() == 2) z[q].resize(0), q--;
      }
    } else
      low[u] = min(low[u], dfn[x]);
  }
}
int main() {
  n = read(), m = read();
  int a, b;
  for (int i = 1; i <= m; i++)
    e[i].u = read(), e[i].t = read(), f[e[i].u][e[i].t] = f[e[i].t][e[i].u] = i,
    v[e[i].u].push_back(e[i].t), v[e[i].t].push_back(e[i].u),
    w[e[i].u].push_back(i), w[e[i].t].push_back(i);
  tarjan(1, 0);
  for (int i = 1; i <= q; i++) {
    cnt[i] = z[i].size();
    for (int j = 0; j < z[i].size(); j++)
      c[j + z[i].size() + 1] = c[j + 1] = z[i][j];
    for (int j = 1; j <= z[i].size(); j++)
      qt[z[i].size() + j] = qt[j] = f[c[j]][c[j + 1]], g1[qt[j]] = i;
    for (int j = 2; j <= z[i].size() * 2; j++) {
      if (qt[j - 1] < qt[j])
        fl[j] = 1;
      else
        fl[j] = 0;
      sum[j] = sum[j - 1] + fl[j];
    }
    int g = 1, a = 0;
    for (int j = 1; j <= z[i].size(); j++) {
      g = max(g, j);
      while (fl[g]) g++;
      if (sum[j + z[i].size() - 1] - sum[g - 1] == 0) fq[i] = 1;
    }
  }
  memset(fl, 0, sizeof(fl));
  for (int i = 1; i <= n; i++) dp1[i] = 1;
  for (int i = m; i >= 1; i--) {
    a = e[i].u, b = e[i].t;
    int z = g1[i];
    if (!fl[z] && z > 0) {
      f1[z] = dp1[a], f2[z] = dp1[b], fl[z] = 1;
    }
    cnt[z]--;
    long long x = dp1[a], y = dp1[b];
    dp1[a] = x + y, dp1[b] = x + y;
    if (cnt[z] == 0 && z > 0 && fq[z]) {
      dp1[a] -= (f1[z] + f2[z]), dp1[b] -= (f1[z] + f2[z]);
    }
  }
  for (int i = 1; i <= n; i++) printf("%lld ", dp1[i] - 1);
  return 0;
}

### Prompt

Please formulate a Cpp solution to the following problem:

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;
const int N = 1e6 + 7;
map<int, int> f[N];
bool fl[N], fq[N];
long long f1[N], f2[N], dp1[N];
int n, m, k, q, c[N], g1[N], qt[N], st[N], low[N], dfn[N], cnt[N], sum[N];
vector<int> v[N], w[N], z[N];
struct edge {
  int u, t, w;
} e[N];
inline int read() {
  int num = 0;
  char g = getchar();
  while (g < 48 || 57 < g) g = getchar();
  while (47 < g && g < 58)
    num = (num << 1) + (num << 3) + g - 48, g = getchar();
  return num;
}
inline void tarjan(int u, int fa) {
  st[++st[0]] = u, low[u] = dfn[u] = ++k;
  int c = st[0];
  for (int i = 0; i < v[u].size(); i++) {
    int x = v[u][i];
    if (x == fa) continue;
    if (!dfn[x]) {
      tarjan(x, u), low[u] = min(low[u], low[x]);
      if (low[x] >= dfn[u]) {
        q++;
        while (st[st[0] + 1] != x) z[q].push_back(st[st[0]]), st[0]--;
        z[q].push_back(u);
        if (z[q].size() == 2) z[q].resize(0), q--;
      }
    } else
      low[u] = min(low[u], dfn[x]);
  }
}
int main() {
  n = read(), m = read();
  int a, b;
  for (int i = 1; i <= m; i++)
    e[i].u = read(), e[i].t = read(), f[e[i].u][e[i].t] = f[e[i].t][e[i].u] = i,
    v[e[i].u].push_back(e[i].t), v[e[i].t].push_back(e[i].u),
    w[e[i].u].push_back(i), w[e[i].t].push_back(i);
  tarjan(1, 0);
  for (int i = 1; i <= q; i++) {
    cnt[i] = z[i].size();
    for (int j = 0; j < z[i].size(); j++)
      c[j + z[i].size() + 1] = c[j + 1] = z[i][j];
    for (int j = 1; j <= z[i].size(); j++)
      qt[z[i].size() + j] = qt[j] = f[c[j]][c[j + 1]], g1[qt[j]] = i;
    for (int j = 2; j <= z[i].size() * 2; j++) {
      if (qt[j - 1] < qt[j])
        fl[j] = 1;
      else
        fl[j] = 0;
      sum[j] = sum[j - 1] + fl[j];
    }
    int g = 1, a = 0;
    for (int j = 1; j <= z[i].size(); j++) {
      g = max(g, j);
      while (fl[g]) g++;
      if (sum[j + z[i].size() - 1] - sum[g - 1] == 0) fq[i] = 1;
    }
  }
  memset(fl, 0, sizeof(fl));
  for (int i = 1; i <= n; i++) dp1[i] = 1;
  for (int i = m; i >= 1; i--) {
    a = e[i].u, b = e[i].t;
    int z = g1[i];
    if (!fl[z] && z > 0) {
      f1[z] = dp1[a], f2[z] = dp1[b], fl[z] = 1;
    }
    cnt[z]--;
    long long x = dp1[a], y = dp1[b];
    dp1[a] = x + y, dp1[b] = x + y;
    if (cnt[z] == 0 && z > 0 && fq[z]) {
      dp1[a] -= (f1[z] + f2[z]), dp1[b] -= (f1[z] + f2[z]);
    }
  }
  for (int i = 1; i <= n; i++) printf("%lld ", dp1[i] - 1);
  return 0;
}

```