#include <bits/stdc++.h>
using namespace std;
const int M = 5e5 + 5;
int read() {
  int x = 0, y = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') y = (ch == '-') ? -1 : 1, ch = getchar();
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
  return x * y;
}
vector<pair<int, int> > G[M];
int cnt = 0, sd[M], cir[M], Max[M], Min[M];
bool can[M];
void work() {
  if (cir[0] == 1) return;
  int x, y;
  cnt++;
  Max[cnt] = 0, Min[cnt] = 1e9;
  for (int i = 1; i <= cir[0]; i++) {
    sd[cir[i]] = cnt;
    if (cir[i] > Max[cnt]) Max[cnt] = cir[i], x = i;
    if (cir[i] < Min[cnt]) Min[cnt] = cir[i], y = i;
  }
  can[cnt] = 1;
  for (int i = 1; i <= cir[0]; i++) cir[i + cir[0]] = cir[i];
  int X = x, Y = y;
  if (x > y) Y += cir[0];
  for (int i = X; i < Y; i++)
    if (cir[i] < cir[i + 1]) can[cnt] = 0;
  X = x, Y = y;
  if (x < y) X += cir[0];
  for (int i = X; i > Y; i--)
    if (cir[i] < cir[i - 1]) can[cnt] = 0;
}
int num = 0, dfn[M], low[M], fa[M], up[M], dp[M], f[M];
void dfs(int u) {
  dfn[u] = low[u] = ++num;
  dp[u] = 1;
  for (auto i : G[u])
    if (i.first != fa[u]) {
      int v = i.first, w = i.second;
      if (!dfn[v])
        fa[v] = u, up[v] = w, dfs(v), low[u] = min(low[u], low[v]);
      else if (dfn[v] == -1) {
        cir[0] = 0;
        for (int x = v; x != u; x = fa[x]) cir[++cir[0]] = up[x];
        cir[++cir[0]] = w, work();
      } else
        low[u] = min(low[u], dfn[v]);
    }
  dfn[u] = -1;
}
struct Edge {
  int x, y;
} e[M];
void solve() {
  int n = read(), m = read();
  for (int i = m; i >= 1; i--) {
    int x = read(), y = read();
    G[x].push_back(make_pair(y, i)), G[y].push_back(make_pair(x, i));
    e[i] = (Edge){x, y};
  }
  dfs(1);
  for (int i = 1; i <= m; i++) {
    int x = e[i].x, y = e[i].y;
    f[i] = dp[x] + dp[y];
    if (can[sd[i]] && i == Max[sd[i]]) f[i] -= f[Min[sd[i]]];
    dp[x] = f[i], dp[y] = f[i];
  }
  for (int i = 1; i <= n; i++) printf("%d ", dp[i] - 1);
}
signed main() { solve(); }

### Prompt

Generate 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 M = 5e5 + 5;
int read() {
  int x = 0, y = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') y = (ch == '-') ? -1 : 1, ch = getchar();
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
  return x * y;
}
vector<pair<int, int> > G[M];
int cnt = 0, sd[M], cir[M], Max[M], Min[M];
bool can[M];
void work() {
  if (cir[0] == 1) return;
  int x, y;
  cnt++;
  Max[cnt] = 0, Min[cnt] = 1e9;
  for (int i = 1; i <= cir[0]; i++) {
    sd[cir[i]] = cnt;
    if (cir[i] > Max[cnt]) Max[cnt] = cir[i], x = i;
    if (cir[i] < Min[cnt]) Min[cnt] = cir[i], y = i;
  }
  can[cnt] = 1;
  for (int i = 1; i <= cir[0]; i++) cir[i + cir[0]] = cir[i];
  int X = x, Y = y;
  if (x > y) Y += cir[0];
  for (int i = X; i < Y; i++)
    if (cir[i] < cir[i + 1]) can[cnt] = 0;
  X = x, Y = y;
  if (x < y) X += cir[0];
  for (int i = X; i > Y; i--)
    if (cir[i] < cir[i - 1]) can[cnt] = 0;
}
int num = 0, dfn[M], low[M], fa[M], up[M], dp[M], f[M];
void dfs(int u) {
  dfn[u] = low[u] = ++num;
  dp[u] = 1;
  for (auto i : G[u])
    if (i.first != fa[u]) {
      int v = i.first, w = i.second;
      if (!dfn[v])
        fa[v] = u, up[v] = w, dfs(v), low[u] = min(low[u], low[v]);
      else if (dfn[v] == -1) {
        cir[0] = 0;
        for (int x = v; x != u; x = fa[x]) cir[++cir[0]] = up[x];
        cir[++cir[0]] = w, work();
      } else
        low[u] = min(low[u], dfn[v]);
    }
  dfn[u] = -1;
}
struct Edge {
  int x, y;
} e[M];
void solve() {
  int n = read(), m = read();
  for (int i = m; i >= 1; i--) {
    int x = read(), y = read();
    G[x].push_back(make_pair(y, i)), G[y].push_back(make_pair(x, i));
    e[i] = (Edge){x, y};
  }
  dfs(1);
  for (int i = 1; i <= m; i++) {
    int x = e[i].x, y = e[i].y;
    f[i] = dp[x] + dp[y];
    if (can[sd[i]] && i == Max[sd[i]]) f[i] -= f[Min[sd[i]]];
    dp[x] = f[i], dp[y] = f[i];
  }
  for (int i = 1; i <= n; i++) printf("%d ", dp[i] - 1);
}
signed main() { solve(); }

```