#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
const int inf = 1000 * 1000 * 1000;
const int mod = 998244353;
int n, m;
vector<pair<int, int> > g[N];
vector<pair<int, pair<int, int> > > E;
bool used[N], mark[N];
vector<int> gcycle[N];
vector<vector<pair<int, int> > > G;
int parent[N], ind[N];
void dfs(int v, int p) {
  used[v] = true;
  for (int i = 0; i < (int)g[v].size(); i++) {
    int to = g[v][i].first;
    int id = g[v][i].second;
    if (to == p || mark[id]) continue;
    if (used[to]) {
      int gag = v;
      vector<pair<int, int> > cycle;
      while (gag != to) {
        cycle.push_back(make_pair(gag, ind[gag]));
        mark[ind[gag]] = true;
        gag = parent[gag];
      }
      mark[id] = true;
      cycle.push_back(make_pair(to, id));
      gcycle[to].push_back((int)G.size());
      G.push_back(cycle);
      continue;
    }
    parent[to] = v;
    ind[to] = id;
    dfs(to, v);
  }
}
int answ[N], pat[N];
int sub[N];
bool check(vector<int> &mas) {
  for (int i = 1; i < (int)mas.size(); i++) {
    if (mas[i] > mas[i - 1]) return false;
  }
  return true;
}
void upd(int id) {
  int mn, mx;
  int id1, id2;
  for (int i = 0; i < (int)G[id].size(); i++) {
    if (i == 0 || G[id][i].second < mn) {
      mn = G[id][i].second;
      id1 = i;
    }
    if (i == 0 || G[id][i].second > mx) {
      mx = G[id][i].second;
      id2 = i;
    }
  }
  vector<int> mas1, mas2;
  if (id2 > id1) {
    for (int i = id2; i > id1; i--) {
      mas1.push_back(G[id][i].second);
    }
    for (int i = id2; i < (int)G[id].size(); i++) {
      mas2.push_back(G[id][i].second);
    }
    for (int i = 0; i < id1; i++) {
      mas2.push_back(G[id][i].second);
    }
  } else {
    for (int i = id2; i < id1; i++) {
      mas1.push_back(G[id][i].second);
    }
    for (int i = id2; i >= 0; i--) {
      mas2.push_back(G[id][i].second);
    }
    for (int i = (int)G[id].size() - 1; i > id1; i--) {
      mas2.push_back(G[id][i].second);
    }
  }
  if (check(mas1) && check(mas2)) {
    sub[mn] = mx;
  }
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    g[a].push_back(make_pair(b, i));
    g[b].push_back(make_pair(a, i));
    E.push_back(make_pair(i, make_pair(a, b)));
  }
  sort(E.begin(), E.end());
  reverse(E.begin(), E.end());
  dfs(1, -1);
  for (int i = 0; i < (int)G.size(); i++) {
    upd(i);
  }
  for (int i = 1; i <= n; i++) {
    answ[i] = 1;
  }
  for (int i = 0; i < (int)E.size(); i++) {
    int a = E[i].second.first;
    int b = E[i].second.second;
    pat[m - i] = answ[a] + answ[b] - pat[sub[m - i]];
    answ[a] = answ[b] = pat[m - i];
  }
  for (int i = 1; i <= n; i++) {
    --answ[i];
    printf("%d ", answ[i]);
  }
  cout << endl;
  return 0;
}

### Prompt

Please formulate 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 N = 500005;
const int inf = 1000 * 1000 * 1000;
const int mod = 998244353;
int n, m;
vector<pair<int, int> > g[N];
vector<pair<int, pair<int, int> > > E;
bool used[N], mark[N];
vector<int> gcycle[N];
vector<vector<pair<int, int> > > G;
int parent[N], ind[N];
void dfs(int v, int p) {
  used[v] = true;
  for (int i = 0; i < (int)g[v].size(); i++) {
    int to = g[v][i].first;
    int id = g[v][i].second;
    if (to == p || mark[id]) continue;
    if (used[to]) {
      int gag = v;
      vector<pair<int, int> > cycle;
      while (gag != to) {
        cycle.push_back(make_pair(gag, ind[gag]));
        mark[ind[gag]] = true;
        gag = parent[gag];
      }
      mark[id] = true;
      cycle.push_back(make_pair(to, id));
      gcycle[to].push_back((int)G.size());
      G.push_back(cycle);
      continue;
    }
    parent[to] = v;
    ind[to] = id;
    dfs(to, v);
  }
}
int answ[N], pat[N];
int sub[N];
bool check(vector<int> &mas) {
  for (int i = 1; i < (int)mas.size(); i++) {
    if (mas[i] > mas[i - 1]) return false;
  }
  return true;
}
void upd(int id) {
  int mn, mx;
  int id1, id2;
  for (int i = 0; i < (int)G[id].size(); i++) {
    if (i == 0 || G[id][i].second < mn) {
      mn = G[id][i].second;
      id1 = i;
    }
    if (i == 0 || G[id][i].second > mx) {
      mx = G[id][i].second;
      id2 = i;
    }
  }
  vector<int> mas1, mas2;
  if (id2 > id1) {
    for (int i = id2; i > id1; i--) {
      mas1.push_back(G[id][i].second);
    }
    for (int i = id2; i < (int)G[id].size(); i++) {
      mas2.push_back(G[id][i].second);
    }
    for (int i = 0; i < id1; i++) {
      mas2.push_back(G[id][i].second);
    }
  } else {
    for (int i = id2; i < id1; i++) {
      mas1.push_back(G[id][i].second);
    }
    for (int i = id2; i >= 0; i--) {
      mas2.push_back(G[id][i].second);
    }
    for (int i = (int)G[id].size() - 1; i > id1; i--) {
      mas2.push_back(G[id][i].second);
    }
  }
  if (check(mas1) && check(mas2)) {
    sub[mn] = mx;
  }
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    g[a].push_back(make_pair(b, i));
    g[b].push_back(make_pair(a, i));
    E.push_back(make_pair(i, make_pair(a, b)));
  }
  sort(E.begin(), E.end());
  reverse(E.begin(), E.end());
  dfs(1, -1);
  for (int i = 0; i < (int)G.size(); i++) {
    upd(i);
  }
  for (int i = 1; i <= n; i++) {
    answ[i] = 1;
  }
  for (int i = 0; i < (int)E.size(); i++) {
    int a = E[i].second.first;
    int b = E[i].second.second;
    pat[m - i] = answ[a] + answ[b] - pat[sub[m - i]];
    answ[a] = answ[b] = pat[m - i];
  }
  for (int i = 1; i <= n; i++) {
    --answ[i];
    printf("%d ", answ[i]);
  }
  cout << endl;
  return 0;
}

```