#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10, mod = 1e9 + 7;
const long long inf = 1e18;
template <typename A, typename B>
ostream& operator<<(ostream& out, pair<A, B> p) {
  out << "{ " << p.first << ", " << p.second << " }";
  return out;
}
template <typename T>
ostream& operator<<(ostream& out, vector<T> v) {
  out << "[ ";
  for (int i = 0; i < int((v).size()); i++) {
    out << v[i];
    if (i != int((v).size()) - 1) out << " ,";
  }
  out << " ]";
  return out;
}
vector<pair<int, int> > ed;
vector<pair<int, int> > v[maxn];
vector<pair<int, int> > cyc[maxn];
bool mark[maxn];
int h[maxn];
pair<int, int> pr[maxn];
void prep(int u, int par = -1) {
  mark[u] = 1;
  for (auto [y, id] : v[u]) {
    if (mark[y]) {
      if (h[y] < h[u] && y != par) {
        vector<pair<int, int> > vec;
        int bst = 0, val = pr[u].second, tmp = u;
        vec.push_back({u, pr[u].second});
        while (tmp != y) {
          tmp = pr[tmp].first;
          int w = (tmp == y ? id : pr[tmp].second);
          vec.push_back({tmp, w});
          if (w < val) val = w, bst = int((vec).size()) - 1;
        }
        for (int i = bst + 1; i < int((vec).size()); i++)
          cyc[val].push_back(vec[i]);
        for (int i = 0; i < bst; i++) cyc[val].push_back(vec[i]);
      }
    } else {
      h[y] = h[u] + 1;
      pr[y] = {u, id};
      prep(y, u);
    }
  }
}
int Lstr[maxn], Lstl[maxn];
int dp[maxn], dpe[maxn];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie();
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    v[a].push_back({b, i});
    v[b].push_back({a, i});
    ed.push_back({a, b});
  }
  prep(1);
  for (int i = 1; i <= n; i++) {
    dp[i] = 1;
  }
  for (int i = m - 1; i >= 0; i--) {
    dp[ed[i].first] = dp[ed[i].second] = dpe[i] =
        dp[ed[i].first] + dp[ed[i].second];
    if (cyc[i].empty() == 0) {
      if (ed[i].second == cyc[i][0].first) swap(ed[i].first, ed[i].second);
      int r = int((cyc[i]).size());
      Lstr[r] = -1;
      while (r > 0 && Lstr[r] < cyc[i][r - 1].second)
        --r, Lstr[r] = cyc[i][r].second;
      int l = 0;
      Lstl[l] = -1;
      while (l < int((cyc[i]).size()) && Lstl[l] < cyc[i][l].second)
        ++l, Lstl[l] = cyc[i][l - 1].second;
      cyc[i].push_back({ed[i].second, 0});
      assert(l < r || l - r == 1);
      if (l - r == 1) {
        for (auto [y, id] : v[cyc[i][r].first])
          if (y == cyc[i][l].first)
            dp[ed[i].first] -= dpe[id], dp[ed[i].second] -= dpe[id];
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    cout << dp[i] - 1 << " ";
  }
  return cout << endl, 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;
const int maxn = 5e5 + 10, mod = 1e9 + 7;
const long long inf = 1e18;
template <typename A, typename B>
ostream& operator<<(ostream& out, pair<A, B> p) {
  out << "{ " << p.first << ", " << p.second << " }";
  return out;
}
template <typename T>
ostream& operator<<(ostream& out, vector<T> v) {
  out << "[ ";
  for (int i = 0; i < int((v).size()); i++) {
    out << v[i];
    if (i != int((v).size()) - 1) out << " ,";
  }
  out << " ]";
  return out;
}
vector<pair<int, int> > ed;
vector<pair<int, int> > v[maxn];
vector<pair<int, int> > cyc[maxn];
bool mark[maxn];
int h[maxn];
pair<int, int> pr[maxn];
void prep(int u, int par = -1) {
  mark[u] = 1;
  for (auto [y, id] : v[u]) {
    if (mark[y]) {
      if (h[y] < h[u] && y != par) {
        vector<pair<int, int> > vec;
        int bst = 0, val = pr[u].second, tmp = u;
        vec.push_back({u, pr[u].second});
        while (tmp != y) {
          tmp = pr[tmp].first;
          int w = (tmp == y ? id : pr[tmp].second);
          vec.push_back({tmp, w});
          if (w < val) val = w, bst = int((vec).size()) - 1;
        }
        for (int i = bst + 1; i < int((vec).size()); i++)
          cyc[val].push_back(vec[i]);
        for (int i = 0; i < bst; i++) cyc[val].push_back(vec[i]);
      }
    } else {
      h[y] = h[u] + 1;
      pr[y] = {u, id};
      prep(y, u);
    }
  }
}
int Lstr[maxn], Lstl[maxn];
int dp[maxn], dpe[maxn];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie();
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    v[a].push_back({b, i});
    v[b].push_back({a, i});
    ed.push_back({a, b});
  }
  prep(1);
  for (int i = 1; i <= n; i++) {
    dp[i] = 1;
  }
  for (int i = m - 1; i >= 0; i--) {
    dp[ed[i].first] = dp[ed[i].second] = dpe[i] =
        dp[ed[i].first] + dp[ed[i].second];
    if (cyc[i].empty() == 0) {
      if (ed[i].second == cyc[i][0].first) swap(ed[i].first, ed[i].second);
      int r = int((cyc[i]).size());
      Lstr[r] = -1;
      while (r > 0 && Lstr[r] < cyc[i][r - 1].second)
        --r, Lstr[r] = cyc[i][r].second;
      int l = 0;
      Lstl[l] = -1;
      while (l < int((cyc[i]).size()) && Lstl[l] < cyc[i][l].second)
        ++l, Lstl[l] = cyc[i][l - 1].second;
      cyc[i].push_back({ed[i].second, 0});
      assert(l < r || l - r == 1);
      if (l - r == 1) {
        for (auto [y, id] : v[cyc[i][r].first])
          if (y == cyc[i][l].first)
            dp[ed[i].first] -= dpe[id], dp[ed[i].second] -= dpe[id];
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    cout << dp[i] - 1 << " ";
  }
  return cout << endl, 0;
}

```