#include <bits/stdc++.h>
using namespace std;
const int maxN = 5e5 + 10;
int n, m;
int x[maxN + 1], y[maxN + 1];
int dep[maxN + 1], pa[maxN + 1], fa[maxN + 1];
int f[maxN + 1], w[maxN + 1], len[maxN + 1];
bool flag[maxN + 1];
vector<pair<int, int> > to[maxN + 1];
inline int read() {
  int num = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) num = (num << 3) + (num << 1) + (ch ^ 48), ch = getchar();
  return num * f;
}
inline int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
inline void dfs(int u, int pa) {
  fa[u] = pa;
  dep[u] = dep[pa] + 1;
  for (int i = 0; i < to[u].size(); i++) {
    int v = to[u][i].first, w = to[u][i].second;
    if (v == pa) continue;
    len[v] = w;
    dfs(v, u);
  }
}
int main() {
  n = read(), m = read();
  for (int i = 1; i <= m; i++) x[i] = read(), y[i] = read();
  for (int i = 1; i <= n; i++) pa[i] = i, f[i] = 1;
  for (int i = m; i >= 1; i--) {
    int fx = find(x[i]), fy = find(y[i]);
    if (fx != fy) {
      to[x[i]].push_back(make_pair(y[i], i));
      to[y[i]].push_back(make_pair(x[i], i));
      pa[fx] = fy;
    } else
      flag[i] = true;
  }
  dfs(1, 0);
  for (int i = m; i >= 1; i--) {
    int tx = x[i], ty = y[i];
    if (!flag[i]) {
      w[i] = f[tx] = f[ty] = f[tx] + f[ty];
      continue;
    }
    vector<int> A, B;
    while (tx != ty) {
      if (dep[tx] > dep[ty]) {
        A.push_back(len[tx]);
        tx = fa[tx];
      } else {
        B.push_back(len[ty]);
        ty = fa[ty];
      }
    }
    for (int j = B.size() - 1; j >= 0; j--) A.push_back(B[j]);
    tx = x[i], ty = y[i];
    int res = f[tx] + f[ty], mx, now = 0;
    while (now + 1 < A.size() && A[now] < A[now + 1]) now++;
    mx = A[now];
    while (now + 1 < A.size() && A[now] > A[now + 1]) now++;
    if (now == A.size() - 1) res -= w[mx];
    w[i] = f[tx] = f[ty] = res;
  }
  for (int i = 1; i <= n; i++) printf("%d ", f[i] - 1);
  puts("");
  return 0;
}

### Prompt

Create a solution in cpp for 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 maxN = 5e5 + 10;
int n, m;
int x[maxN + 1], y[maxN + 1];
int dep[maxN + 1], pa[maxN + 1], fa[maxN + 1];
int f[maxN + 1], w[maxN + 1], len[maxN + 1];
bool flag[maxN + 1];
vector<pair<int, int> > to[maxN + 1];
inline int read() {
  int num = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) num = (num << 3) + (num << 1) + (ch ^ 48), ch = getchar();
  return num * f;
}
inline int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
inline void dfs(int u, int pa) {
  fa[u] = pa;
  dep[u] = dep[pa] + 1;
  for (int i = 0; i < to[u].size(); i++) {
    int v = to[u][i].first, w = to[u][i].second;
    if (v == pa) continue;
    len[v] = w;
    dfs(v, u);
  }
}
int main() {
  n = read(), m = read();
  for (int i = 1; i <= m; i++) x[i] = read(), y[i] = read();
  for (int i = 1; i <= n; i++) pa[i] = i, f[i] = 1;
  for (int i = m; i >= 1; i--) {
    int fx = find(x[i]), fy = find(y[i]);
    if (fx != fy) {
      to[x[i]].push_back(make_pair(y[i], i));
      to[y[i]].push_back(make_pair(x[i], i));
      pa[fx] = fy;
    } else
      flag[i] = true;
  }
  dfs(1, 0);
  for (int i = m; i >= 1; i--) {
    int tx = x[i], ty = y[i];
    if (!flag[i]) {
      w[i] = f[tx] = f[ty] = f[tx] + f[ty];
      continue;
    }
    vector<int> A, B;
    while (tx != ty) {
      if (dep[tx] > dep[ty]) {
        A.push_back(len[tx]);
        tx = fa[tx];
      } else {
        B.push_back(len[ty]);
        ty = fa[ty];
      }
    }
    for (int j = B.size() - 1; j >= 0; j--) A.push_back(B[j]);
    tx = x[i], ty = y[i];
    int res = f[tx] + f[ty], mx, now = 0;
    while (now + 1 < A.size() && A[now] < A[now + 1]) now++;
    mx = A[now];
    while (now + 1 < A.size() && A[now] > A[now + 1]) now++;
    if (now == A.size() - 1) res -= w[mx];
    w[i] = f[tx] = f[ty] = res;
  }
  for (int i = 1; i <= n; i++) printf("%d ", f[i] - 1);
  puts("");
  return 0;
}

```