#include <bits/stdc++.h>
using namespace std;
struct Vertex {
  int r;
  int f;
};
vector<Vertex> snm;
int get(int v) {
  if (snm[v].f != v) snm[v].f = get(snm[v].f);
  return snm[v].f;
}
void unite(int u, int v) {
  if (snm[u].r > snm[v].r) swap(u, v);
  snm[u].f = v;
  if (snm[u].r == snm[v].r) snm[v].r++;
}
vector<vector<pair<int, int> > > data;
vector<bool> good;
vector<int> father, tin, tout;
vector<int> gof;
int cur = 0;
void dfs(int vertex, int last) {
  father[vertex] = last;
  tin[vertex] = cur++;
  for (int i = 0; i < data[vertex].size(); ++i) {
    int to = data[vertex][i].first, num = data[vertex][i].second;
    if (!good[num] || last == to) continue;
    gof[to] = num;
    dfs(to, vertex);
  }
  tout[vertex] = cur++;
}
bool isf(int u, int v) { return (tin[u] <= tin[v] && tout[u] >= tout[v]); }
vector<int> get_path(int u, int v) {
  vector<int> ed;
  int t = u;
  while (!isf(u, v)) {
    ed.push_back(gof[u]);
    u = father[u];
  }
  vector<int> ted;
  while (!isf(v, t)) {
    ted.push_back(gof[v]);
    v = father[v];
  }
  reverse(ted.begin(), ted.end());
  for (int i = 0; i < ted.size(); ++i) ed.push_back(ted[i]);
  return ed;
}
int get_min(vector<int> v) {
  int index = min_element(v.begin(), v.end()) - v.begin();
  bool good = true;
  for (int i = 0; i + 1 <= index; ++i) {
    if (v[i] < v[i + 1]) good = false;
  }
  for (int i = index; i + 1 < v.size(); ++i) {
    if (v[i] > v[i + 1]) good = false;
  }
  if (!good) return -1;
  return v[index];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  father.assign(n, -1), tin.assign(n, -1), tout.assign(n, -1),
      gof.assign(n, -1);
  for (int i = 0; i < n; ++i) {
    snm.push_back({1, i});
  }
  vector<pair<int, int> > edges;
  data.assign(n, {}), good.assign(m, false);
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    edges.push_back({u, v});
  }
  reverse(edges.begin(), edges.end());
  for (int i = 0; i < m; ++i) {
    int u = edges[i].first, v = edges[i].second;
    data[u].push_back({v, i});
    data[v].push_back({u, i});
    int A = get(u), B = get(v);
    good[i] = (A != B);
    if (A != B) unite(A, B);
  }
  dfs(0, -1);
  vector<int> ans(n, 1);
  vector<int> edans(m);
  for (int i = 0; i < m; ++i) {
    int u = edges[i].first, v = edges[i].second;
    if (good[i]) {
      int sum = ans[u] + ans[v];
      ans[u] = sum, ans[v] = sum, edans[i] = sum;
    } else {
      vector<int> P = get_path(u, v);
      int W = get_min(P);
      int sum = ans[u] + ans[v];
      if (W != -1) sum = ans[u] + ans[v] - edans[W];
      ans[u] = sum, ans[v] = sum, edans[i] = sum;
    }
  }
  for (int i = 0; i < n; ++i) cout << ans[i] - 1 << " ";
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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;
struct Vertex {
  int r;
  int f;
};
vector<Vertex> snm;
int get(int v) {
  if (snm[v].f != v) snm[v].f = get(snm[v].f);
  return snm[v].f;
}
void unite(int u, int v) {
  if (snm[u].r > snm[v].r) swap(u, v);
  snm[u].f = v;
  if (snm[u].r == snm[v].r) snm[v].r++;
}
vector<vector<pair<int, int> > > data;
vector<bool> good;
vector<int> father, tin, tout;
vector<int> gof;
int cur = 0;
void dfs(int vertex, int last) {
  father[vertex] = last;
  tin[vertex] = cur++;
  for (int i = 0; i < data[vertex].size(); ++i) {
    int to = data[vertex][i].first, num = data[vertex][i].second;
    if (!good[num] || last == to) continue;
    gof[to] = num;
    dfs(to, vertex);
  }
  tout[vertex] = cur++;
}
bool isf(int u, int v) { return (tin[u] <= tin[v] && tout[u] >= tout[v]); }
vector<int> get_path(int u, int v) {
  vector<int> ed;
  int t = u;
  while (!isf(u, v)) {
    ed.push_back(gof[u]);
    u = father[u];
  }
  vector<int> ted;
  while (!isf(v, t)) {
    ted.push_back(gof[v]);
    v = father[v];
  }
  reverse(ted.begin(), ted.end());
  for (int i = 0; i < ted.size(); ++i) ed.push_back(ted[i]);
  return ed;
}
int get_min(vector<int> v) {
  int index = min_element(v.begin(), v.end()) - v.begin();
  bool good = true;
  for (int i = 0; i + 1 <= index; ++i) {
    if (v[i] < v[i + 1]) good = false;
  }
  for (int i = index; i + 1 < v.size(); ++i) {
    if (v[i] > v[i + 1]) good = false;
  }
  if (!good) return -1;
  return v[index];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  father.assign(n, -1), tin.assign(n, -1), tout.assign(n, -1),
      gof.assign(n, -1);
  for (int i = 0; i < n; ++i) {
    snm.push_back({1, i});
  }
  vector<pair<int, int> > edges;
  data.assign(n, {}), good.assign(m, false);
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    edges.push_back({u, v});
  }
  reverse(edges.begin(), edges.end());
  for (int i = 0; i < m; ++i) {
    int u = edges[i].first, v = edges[i].second;
    data[u].push_back({v, i});
    data[v].push_back({u, i});
    int A = get(u), B = get(v);
    good[i] = (A != B);
    if (A != B) unite(A, B);
  }
  dfs(0, -1);
  vector<int> ans(n, 1);
  vector<int> edans(m);
  for (int i = 0; i < m; ++i) {
    int u = edges[i].first, v = edges[i].second;
    if (good[i]) {
      int sum = ans[u] + ans[v];
      ans[u] = sum, ans[v] = sum, edans[i] = sum;
    } else {
      vector<int> P = get_path(u, v);
      int W = get_min(P);
      int sum = ans[u] + ans[v];
      if (W != -1) sum = ans[u] + ans[v] - edans[W];
      ans[u] = sum, ans[v] = sum, edans[i] = sum;
    }
  }
  for (int i = 0; i < n; ++i) cout << ans[i] - 1 << " ";
}

```