#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target( \
    "avx,avx2,fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
long long MOD = 1e9 + 7;
long long INF = 1e18;
const int N = 500001;
vector<long long> gr[N];
vector<pair<long long, long long> > gr2[N];
vector<vector<long long> > cyc;
pair<long long, long long> pr[N];
long long used[N];
long long h[N];
long long kolll = 0;
void dfs(long long v, pair<long long, long long> p) {
  pr[v] = p;
  used[v] = 1;
  h[v] = h[p.first] + 1;
  for (auto i : gr2[v]) {
    if (!used[i.first]) {
      dfs(i.first, {v, i.second});
    } else {
      if (i.first != p.first && h[i.first] < h[v]) {
        vector<long long> cy;
        cy.push_back(i.second);
        long long nw = v;
        while (nw != i.first) {
          cy.push_back(pr[nw].second);
          nw = pr[nw].first;
        }
        cyc.push_back(cy);
      }
    }
  }
}
void get() { dfs(0, {0, 0}); }
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0),
      cout << fixed << setprecision(20);
  long long n, m;
  cin >> n >> m;
  vector<long long> a(m);
  vector<long long> b(m);
  for (int i = 0; i < m; i++) {
    cin >> a[i] >> b[i];
    a[i]--, b[i]--;
    gr[a[i]].push_back(b[i]);
    gr2[a[i]].push_back({b[i], i});
    gr[b[i]].push_back(a[i]);
    gr2[b[i]].push_back({a[i], i});
  }
  vector<long long> f(m);
  vector<long long> ans(n, 1);
  vector<long long> sub(m, -1);
  get();
  for (auto cy : cyc) {
    long long mx = -1;
    long long mn = MOD;
    long long mnnum = -1;
    for (int j = 0; j < cy.size(); j++) {
      auto i = cy[j];
      mn = min(i, mn);
      if (i == mn) {
        mnnum = j;
      }
      mx = max(i, mx);
    }
    long long nw = mnnum;
    long long ok = 1;
    while (cy[nw] != mx) {
      if (cy[nw] > cy[(nw + 1) % ((long long)cy.size())]) {
        ok = 0;
      }
      nw = (nw + 1) % ((long long)cy.size());
    }
    nw = mnnum;
    while (cy[nw] != mx) {
      if (cy[nw] >
          cy[(nw - 1 + ((long long)cy.size())) % ((long long)(cy.size()))]) {
        ok = 0;
      }
      nw = (nw - 1 + ((long long)cy.size())) % ((long long)cy.size());
    }
    if (ok) {
      sub[mn] = mx;
    }
  }
  for (int i = m - 1; i > -1; i--) {
    if (sub[i] != -1) {
      sub[i] = f[sub[i]];
    } else {
      sub[i] = 0;
    }
    f[i] = ans[a[i]] + ans[b[i]] - sub[i];
    ans[a[i]] = ans[b[i]] = f[i];
  }
  for (int i = 0; i < n; i++) {
    cout << ans[i] - 1 << " ";
  }
}

### Prompt

Develop a solution in cpp to the problem described below:

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>
#pragma GCC optimize("Ofast")
#pragma GCC target( \
    "avx,avx2,fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
long long MOD = 1e9 + 7;
long long INF = 1e18;
const int N = 500001;
vector<long long> gr[N];
vector<pair<long long, long long> > gr2[N];
vector<vector<long long> > cyc;
pair<long long, long long> pr[N];
long long used[N];
long long h[N];
long long kolll = 0;
void dfs(long long v, pair<long long, long long> p) {
  pr[v] = p;
  used[v] = 1;
  h[v] = h[p.first] + 1;
  for (auto i : gr2[v]) {
    if (!used[i.first]) {
      dfs(i.first, {v, i.second});
    } else {
      if (i.first != p.first && h[i.first] < h[v]) {
        vector<long long> cy;
        cy.push_back(i.second);
        long long nw = v;
        while (nw != i.first) {
          cy.push_back(pr[nw].second);
          nw = pr[nw].first;
        }
        cyc.push_back(cy);
      }
    }
  }
}
void get() { dfs(0, {0, 0}); }
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0),
      cout << fixed << setprecision(20);
  long long n, m;
  cin >> n >> m;
  vector<long long> a(m);
  vector<long long> b(m);
  for (int i = 0; i < m; i++) {
    cin >> a[i] >> b[i];
    a[i]--, b[i]--;
    gr[a[i]].push_back(b[i]);
    gr2[a[i]].push_back({b[i], i});
    gr[b[i]].push_back(a[i]);
    gr2[b[i]].push_back({a[i], i});
  }
  vector<long long> f(m);
  vector<long long> ans(n, 1);
  vector<long long> sub(m, -1);
  get();
  for (auto cy : cyc) {
    long long mx = -1;
    long long mn = MOD;
    long long mnnum = -1;
    for (int j = 0; j < cy.size(); j++) {
      auto i = cy[j];
      mn = min(i, mn);
      if (i == mn) {
        mnnum = j;
      }
      mx = max(i, mx);
    }
    long long nw = mnnum;
    long long ok = 1;
    while (cy[nw] != mx) {
      if (cy[nw] > cy[(nw + 1) % ((long long)cy.size())]) {
        ok = 0;
      }
      nw = (nw + 1) % ((long long)cy.size());
    }
    nw = mnnum;
    while (cy[nw] != mx) {
      if (cy[nw] >
          cy[(nw - 1 + ((long long)cy.size())) % ((long long)(cy.size()))]) {
        ok = 0;
      }
      nw = (nw - 1 + ((long long)cy.size())) % ((long long)cy.size());
    }
    if (ok) {
      sub[mn] = mx;
    }
  }
  for (int i = m - 1; i > -1; i--) {
    if (sub[i] != -1) {
      sub[i] = f[sub[i]];
    } else {
      sub[i] = 0;
    }
    f[i] = ans[a[i]] + ans[b[i]] - sub[i];
    ans[a[i]] = ans[b[i]] = f[i];
  }
  for (int i = 0; i < n; i++) {
    cout << ans[i] - 1 << " ";
  }
}

```