#include <bits/stdc++.h>
using namespace std;
template <class T>
bool uin(T &a, T b) {
  return a > b ? (a = b, true) : false;
}
template <class T>
bool uax(T &a, T b) {
  return a < b ? (a = b, true) : false;
}
const int maxn = 1010000;
struct TEdge {
  int from, to;
};
vector<TEdge> edges;
vector<int> e[maxn];
int tin[maxn], up[maxn], vis[maxn];
int hapv[maxn], hape[maxn];
int part[maxn];
int n, m;
vector<int> st;
int T = 0;
void dfs(int v, int p) {
  tin[v] = T++;
  up[v] = tin[v];
  vis[v] = 1;
  for (int ei : e[v]) {
    if (ei / 2 == p) continue;
    int u = edges[ei].to;
    if (vis[u] == 1)
      st.push_back(ei), uin(up[v], tin[u]);
    else if (vis[u] == 0) {
      st.push_back(ei);
      dfs(u, ei / 2);
      uin(up[v], up[u]);
      if (up[u] >= tin[v]) {
        vector<int> C;
        while (1) {
          C.push_back(st.back());
          st.pop_back();
          if (C.back() == ei) break;
        }
        if (C.size() != 1) {
          int x = min_element((C).begin(), (C).end()) - C.begin();
          int y = max_element((C).begin(), (C).end()) - C.begin();
          int ex = 0;
          for (int i = 0; i < (int)(C.size()); ++i) {
            int u = C[i], v = C[(i + 1) % C.size()], w = C[(i + 2) % C.size()];
            if ((v < u) == (v < w)) ++ex;
          }
          if (ex == 2) part[C[x] / 2] = C[y] / 2;
        }
      }
    }
  }
  vis[v] = 2;
}
void addEdge(int v, int u) {
  e[v].push_back(edges.size());
  edges.push_back({v, u});
  e[u].push_back(edges.size());
  edges.push_back({u, v});
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(10);
  cout << fixed;
  cin >> n >> m;
  for (int i = 0; i < (int)(m); ++i) {
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    addEdge(u, v);
  }
  for (int i = 0; i < (int)(m); ++i) part[i] = -1;
  dfs(0, -1);
  for (int i = 0; i < (int)(n); ++i) hapv[i] = 1;
  for (int i = (int)(m)-1; i >= 0; --i) {
    int v = edges[2 * i].from, u = edges[2 * i].to;
    int s = hapv[v] + hapv[u];
    hape[i] = s;
    if (part[i] != -1) s -= hape[part[i]];
    hapv[v] = hapv[u] = s;
  }
  for (int i = 0; i < (int)(n); ++i) cout << hapv[i] - 1 << ' ';
  cout << '\n';
  return 0;
}

### Prompt

Your challenge is to write 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 <class T>
bool uin(T &a, T b) {
  return a > b ? (a = b, true) : false;
}
template <class T>
bool uax(T &a, T b) {
  return a < b ? (a = b, true) : false;
}
const int maxn = 1010000;
struct TEdge {
  int from, to;
};
vector<TEdge> edges;
vector<int> e[maxn];
int tin[maxn], up[maxn], vis[maxn];
int hapv[maxn], hape[maxn];
int part[maxn];
int n, m;
vector<int> st;
int T = 0;
void dfs(int v, int p) {
  tin[v] = T++;
  up[v] = tin[v];
  vis[v] = 1;
  for (int ei : e[v]) {
    if (ei / 2 == p) continue;
    int u = edges[ei].to;
    if (vis[u] == 1)
      st.push_back(ei), uin(up[v], tin[u]);
    else if (vis[u] == 0) {
      st.push_back(ei);
      dfs(u, ei / 2);
      uin(up[v], up[u]);
      if (up[u] >= tin[v]) {
        vector<int> C;
        while (1) {
          C.push_back(st.back());
          st.pop_back();
          if (C.back() == ei) break;
        }
        if (C.size() != 1) {
          int x = min_element((C).begin(), (C).end()) - C.begin();
          int y = max_element((C).begin(), (C).end()) - C.begin();
          int ex = 0;
          for (int i = 0; i < (int)(C.size()); ++i) {
            int u = C[i], v = C[(i + 1) % C.size()], w = C[(i + 2) % C.size()];
            if ((v < u) == (v < w)) ++ex;
          }
          if (ex == 2) part[C[x] / 2] = C[y] / 2;
        }
      }
    }
  }
  vis[v] = 2;
}
void addEdge(int v, int u) {
  e[v].push_back(edges.size());
  edges.push_back({v, u});
  e[u].push_back(edges.size());
  edges.push_back({u, v});
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(10);
  cout << fixed;
  cin >> n >> m;
  for (int i = 0; i < (int)(m); ++i) {
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    addEdge(u, v);
  }
  for (int i = 0; i < (int)(m); ++i) part[i] = -1;
  dfs(0, -1);
  for (int i = 0; i < (int)(n); ++i) hapv[i] = 1;
  for (int i = (int)(m)-1; i >= 0; --i) {
    int v = edges[2 * i].from, u = edges[2 * i].to;
    int s = hapv[v] + hapv[u];
    hape[i] = s;
    if (part[i] != -1) s -= hape[part[i]];
    hapv[v] = hapv[u] = s;
  }
  for (int i = 0; i < (int)(n); ++i) cout << hapv[i] - 1 << ' ';
  cout << '\n';
  return 0;
}

```