#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 2;
vector<pair<int, int> > adj[N], adj1[N];
vector<pair<pair<int, int>, int> > lis[N];
int grp[N], head[N], now = 0, level[N], ans[N], dp[N];
pair<int, int> par[N], edge[N];
bool used[N];
vector<int> temp;
int findd(int x) {
  if (head[x] < 0) {
    return x;
  }
  int y = findd(head[x]);
  head[x] = y;
  return y;
}
void unionn(int x, int y) {
  x = findd(x), y = findd(y);
  head[x] += head[y];
  head[y] = x;
}
bool samee(int x, int y) { return findd(x) == findd(y); }
void dfs(int x, int idx) {
  used[x] = true;
  for (auto i : adj[x]) {
    if (!used[i.first]) {
      par[i.first] = {x, i.second};
      level[i.first] = level[x] + 1;
      dfs(i.first, i.second);
    } else {
      if (i.second != idx && level[i.first] < level[x]) {
        now++;
        int temp = x;
        while (temp != i.first) {
          lis[now].push_back({{temp, par[temp].first}, par[temp].second});
          grp[par[temp].second] = now;
          temp = par[temp].first;
        }
        lis[now].push_back({{x, i.first}, i.second});
      }
    }
  }
}
void dfs1(int x, int idx) {
  for (auto i : adj1[x]) {
    if (i.second != idx) {
      temp.push_back(i.second);
      dfs1(i.first, i.second);
    }
  }
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, i, j, k, l, m;
  cin >> n >> m;
  for (i = 1; i <= m; i++) {
    cin >> j >> k;
    edge[i] = {j, k};
    adj[j].push_back({k, i});
    adj[k].push_back({j, i});
  }
  for (i = 1; i <= n; i++) {
    head[i] = -1;
    dp[i] = 1;
  }
  dfs(1, 0);
  for (i = m; i > 0; i--) {
    ans[i] = dp[edge[i].first] + dp[edge[i].second];
    if (!samee(edge[i].first, edge[i].second)) {
      unionn(edge[i].first, edge[i].second);
    } else {
      int idx = grp[i], max1 = 0;
      for (j = 0; j < lis[idx].size(); j++) {
        if (lis[idx][j].second == i) {
          continue;
        }
        adj1[lis[idx][j].first.first].push_back(
            {lis[idx][j].first.second, lis[idx][j].second});
        adj1[lis[idx][j].first.second].push_back(
            {lis[idx][j].first.first, lis[idx][j].second});
        max1 = max(max1, lis[idx][j].second);
      }
      dfs1(edge[i].first, 0);
      j = 0;
      while (j + 1 < temp.size() && temp[j + 1] > temp[j]) {
        j++;
      }
      k = temp.size() - 1;
      while (k > 0 && temp[k - 1] > temp[k]) {
        k--;
      }
      if (j == k) {
        ans[i] -= ans[max1];
      }
      temp.clear();
      for (j = 0; j < lis[idx].size(); j++) {
        if (lis[idx][j].second == i) {
          continue;
        }
        adj1[lis[idx][j].first.first].pop_back();
        adj1[lis[idx][j].first.second].pop_back();
      }
    }
    dp[edge[i].first] = dp[edge[i].second] = ans[i];
  }
  for (i = 1; i <= n; i++) {
    cout << dp[i] - 1 << ' ';
  }
}

### Prompt

Please provide a CPP coded solution 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>
using namespace std;
const int N = 5e5 + 2;
vector<pair<int, int> > adj[N], adj1[N];
vector<pair<pair<int, int>, int> > lis[N];
int grp[N], head[N], now = 0, level[N], ans[N], dp[N];
pair<int, int> par[N], edge[N];
bool used[N];
vector<int> temp;
int findd(int x) {
  if (head[x] < 0) {
    return x;
  }
  int y = findd(head[x]);
  head[x] = y;
  return y;
}
void unionn(int x, int y) {
  x = findd(x), y = findd(y);
  head[x] += head[y];
  head[y] = x;
}
bool samee(int x, int y) { return findd(x) == findd(y); }
void dfs(int x, int idx) {
  used[x] = true;
  for (auto i : adj[x]) {
    if (!used[i.first]) {
      par[i.first] = {x, i.second};
      level[i.first] = level[x] + 1;
      dfs(i.first, i.second);
    } else {
      if (i.second != idx && level[i.first] < level[x]) {
        now++;
        int temp = x;
        while (temp != i.first) {
          lis[now].push_back({{temp, par[temp].first}, par[temp].second});
          grp[par[temp].second] = now;
          temp = par[temp].first;
        }
        lis[now].push_back({{x, i.first}, i.second});
      }
    }
  }
}
void dfs1(int x, int idx) {
  for (auto i : adj1[x]) {
    if (i.second != idx) {
      temp.push_back(i.second);
      dfs1(i.first, i.second);
    }
  }
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, i, j, k, l, m;
  cin >> n >> m;
  for (i = 1; i <= m; i++) {
    cin >> j >> k;
    edge[i] = {j, k};
    adj[j].push_back({k, i});
    adj[k].push_back({j, i});
  }
  for (i = 1; i <= n; i++) {
    head[i] = -1;
    dp[i] = 1;
  }
  dfs(1, 0);
  for (i = m; i > 0; i--) {
    ans[i] = dp[edge[i].first] + dp[edge[i].second];
    if (!samee(edge[i].first, edge[i].second)) {
      unionn(edge[i].first, edge[i].second);
    } else {
      int idx = grp[i], max1 = 0;
      for (j = 0; j < lis[idx].size(); j++) {
        if (lis[idx][j].second == i) {
          continue;
        }
        adj1[lis[idx][j].first.first].push_back(
            {lis[idx][j].first.second, lis[idx][j].second});
        adj1[lis[idx][j].first.second].push_back(
            {lis[idx][j].first.first, lis[idx][j].second});
        max1 = max(max1, lis[idx][j].second);
      }
      dfs1(edge[i].first, 0);
      j = 0;
      while (j + 1 < temp.size() && temp[j + 1] > temp[j]) {
        j++;
      }
      k = temp.size() - 1;
      while (k > 0 && temp[k - 1] > temp[k]) {
        k--;
      }
      if (j == k) {
        ans[i] -= ans[max1];
      }
      temp.clear();
      for (j = 0; j < lis[idx].size(); j++) {
        if (lis[idx][j].second == i) {
          continue;
        }
        adj1[lis[idx][j].first.first].pop_back();
        adj1[lis[idx][j].first.second].pop_back();
      }
    }
    dp[edge[i].first] = dp[edge[i].second] = ans[i];
  }
  for (i = 1; i <= n; i++) {
    cout << dp[i] - 1 << ' ';
  }
}

```