#include <bits/stdc++.h>
using namespace std;
template <typename _T>
inline void _DBG(const char *s, _T x) {
  cerr << s << " = " << x << "\n";
}
template <typename _T, typename... args>
void _DBG(const char *s, _T x, args... a) {
  while (*s != ',') cerr << *s++;
  cerr << " = " << x << ',';
  _DBG(s + 1, a...);
}
const int N = 5e5 + 7;
int n, m, par[N], pre[N], post[N], cnt;
bool check[N];
pair<int, int> memo[N];
vector<pair<int, int> > G[N], T[N], edges;
long long ans[N], eans[N];
int Find(int x) {
  if (par[x] == x) return x;
  return par[x] = Find(par[x]);
}
void Union(int a, int b) { par[Find(a)] = Find(b); }
void dfs(int v, int f = 0) {
  pre[v] = ++cnt;
  for (auto [u, i] : T[v]) {
    if (u != f) {
      dfs(u, v);
      memo[u] = {v, i};
    }
  }
  post[v] = ++cnt;
}
bool anc(int a, int b) { return pre[a] <= pre[b] && post[b] <= post[a]; }
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    par[i] = i;
    ans[i] = 1;
  }
  edges.push_back({0, 0});
  for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    G[a].push_back({b, i});
    G[b].push_back({a, i});
    edges.push_back({a, b});
  }
  for (int i = m; i >= 1; i--) {
    auto [a, b] = edges[i];
    if (Find(a) != Find(b)) {
      Union(a, b);
      T[a].push_back({b, i});
      T[b].push_back({a, i});
    } else
      check[i] = true;
  }
  dfs(1);
  for (int i = m; i >= 1; i--) {
    auto [a, b] = edges[i];
    if (!check[i]) {
      long long x = ans[a] + ans[b];
      ans[a] = ans[b] = x;
      eans[i] = x;
    } else {
      long long x = ans[a] + ans[b];
      int mx = 0;
      vector<pair<int, int> > pa, pb;
      int v = a;
      while (!anc(v, b)) {
        pa.push_back(memo[v]);
        mx = max(mx, memo[v].second);
        v = memo[v].first;
      }
      v = b;
      while (!anc(v, a)) {
        pb.push_back({v, memo[v].second});
        mx = max(mx, memo[v].second);
        v = memo[v].first;
      }
      reverse((pb).begin(), (pb).end());
      for (auto p : pb) pa.push_back(p);
      bool inc1 = true;
      int last1 = 0, ver1 = 0;
      for (auto p : pa) {
        if (last1 > p.second) inc1 = false;
        last1 = p.second;
        if (p.second == mx) {
          ver1 = p.second;
          break;
        }
      }
      bool inc2 = true;
      int last2 = 0, ver2 = 0;
      reverse((pa).begin(), (pa).end());
      for (int i = 0; i < (int)(pa).size(); i++) {
        auto p = pa[i];
        if (last2 > p.second) inc2 = false;
        last2 = p.second;
        if (p.second == mx) {
          ver2 = p.second;
          break;
        }
      }
      if (inc1 && inc2) {
        long long aux = x - eans[ver2];
        ans[b] = x - eans[ver1];
        ans[a] = aux;
        eans[i] = x - eans[ver1];
      } else {
        ans[a] = ans[b] = x;
        eans[i] = x;
      }
    }
  }
  for (int i = 1; i <= n; i++) cout << ans[i] - 1 << " ";
  cout << "\n";
  return 0;
}

### 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;
template <typename _T>
inline void _DBG(const char *s, _T x) {
  cerr << s << " = " << x << "\n";
}
template <typename _T, typename... args>
void _DBG(const char *s, _T x, args... a) {
  while (*s != ',') cerr << *s++;
  cerr << " = " << x << ',';
  _DBG(s + 1, a...);
}
const int N = 5e5 + 7;
int n, m, par[N], pre[N], post[N], cnt;
bool check[N];
pair<int, int> memo[N];
vector<pair<int, int> > G[N], T[N], edges;
long long ans[N], eans[N];
int Find(int x) {
  if (par[x] == x) return x;
  return par[x] = Find(par[x]);
}
void Union(int a, int b) { par[Find(a)] = Find(b); }
void dfs(int v, int f = 0) {
  pre[v] = ++cnt;
  for (auto [u, i] : T[v]) {
    if (u != f) {
      dfs(u, v);
      memo[u] = {v, i};
    }
  }
  post[v] = ++cnt;
}
bool anc(int a, int b) { return pre[a] <= pre[b] && post[b] <= post[a]; }
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    par[i] = i;
    ans[i] = 1;
  }
  edges.push_back({0, 0});
  for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    G[a].push_back({b, i});
    G[b].push_back({a, i});
    edges.push_back({a, b});
  }
  for (int i = m; i >= 1; i--) {
    auto [a, b] = edges[i];
    if (Find(a) != Find(b)) {
      Union(a, b);
      T[a].push_back({b, i});
      T[b].push_back({a, i});
    } else
      check[i] = true;
  }
  dfs(1);
  for (int i = m; i >= 1; i--) {
    auto [a, b] = edges[i];
    if (!check[i]) {
      long long x = ans[a] + ans[b];
      ans[a] = ans[b] = x;
      eans[i] = x;
    } else {
      long long x = ans[a] + ans[b];
      int mx = 0;
      vector<pair<int, int> > pa, pb;
      int v = a;
      while (!anc(v, b)) {
        pa.push_back(memo[v]);
        mx = max(mx, memo[v].second);
        v = memo[v].first;
      }
      v = b;
      while (!anc(v, a)) {
        pb.push_back({v, memo[v].second});
        mx = max(mx, memo[v].second);
        v = memo[v].first;
      }
      reverse((pb).begin(), (pb).end());
      for (auto p : pb) pa.push_back(p);
      bool inc1 = true;
      int last1 = 0, ver1 = 0;
      for (auto p : pa) {
        if (last1 > p.second) inc1 = false;
        last1 = p.second;
        if (p.second == mx) {
          ver1 = p.second;
          break;
        }
      }
      bool inc2 = true;
      int last2 = 0, ver2 = 0;
      reverse((pa).begin(), (pa).end());
      for (int i = 0; i < (int)(pa).size(); i++) {
        auto p = pa[i];
        if (last2 > p.second) inc2 = false;
        last2 = p.second;
        if (p.second == mx) {
          ver2 = p.second;
          break;
        }
      }
      if (inc1 && inc2) {
        long long aux = x - eans[ver2];
        ans[b] = x - eans[ver1];
        ans[a] = aux;
        eans[i] = x - eans[ver1];
      } else {
        ans[a] = ans[b] = x;
        eans[i] = x;
      }
    }
  }
  for (int i = 1; i <= n; i++) cout << ans[i] - 1 << " ";
  cout << "\n";
  return 0;
}

```