#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c* x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  template <class c>
  debug& operator<<(const c&) {
    return *this;
  }
};
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
const int kMaxN = 7e5;
struct FU {
  vi parent;
  FU(int n) : parent(n) { iota((parent).begin(), (parent).end(), 0); }
  int Find(int v) {
    if (parent[v] == v) {
      return v;
    }
    return parent[v] = Find(parent[v]);
  }
  bool Union(int u, int v) {
    u = Find(u);
    v = Find(v);
    if (u != v) {
      parent[u] = v;
      return true;
    }
    return false;
  }
};
int num_reach[kMaxN];
vector<pii> adj[kMaxN];
int n, m;
vector<pii> tree[kMaxN];
int pre[kMaxN], post[kMaxN], ctm;
pii pnt[kMaxN];
void Dfs(int v, int p) {
  debug() << "Dfs "
          << " ["
          << "v"
             ": "
          << (v) << "] "
          << " ["
          << "p"
             ": "
          << (p) << "] ";
  pre[v] = ctm++;
  for (auto& edge : tree[v]) {
    int s = edge.first;
    if (s == p) {
      continue;
    }
    pnt[s] = pii(v, edge.second);
    Dfs(s, v);
  }
  post[v] = ctm;
}
bool Par(int p, int v) { return pre[p] <= pre[v] && post[v] <= post[p]; }
vector<pii> Path(int a, int b) {
  debug() << "Path "
          << " ["
          << "a"
             ": "
          << (a) << "] "
          << " ["
          << "b"
             ": "
          << (b) << "] ";
  vector<pii> xxx, suf;
  while (!Par(a, b) && !Par(b, a)) {
    debug() << " ["
            << "a"
               ": "
            << (a) << "] "
            << " ["
            << "b"
               ": "
            << (b) << "] "
            << " ["
            << "pnt[a]"
               ": "
            << (pnt[a]) << "] ";
    xxx.push_back(pnt[a]);
    a = pnt[a].first;
  }
  while (!Par(a, b)) {
    xxx.push_back(pnt[a]);
    a = pnt[a].first;
  }
  while (!Par(b, a)) {
    suf.push_back(pii(b, pnt[b].second));
    b = pnt[b].first;
  }
  reverse((suf).begin(), (suf).end());
  for (auto x : suf) xxx.push_back(x);
  return xxx;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
  cin >> n >> m;
  vector<pii> order;
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    order.emplace_back(u, v);
    adj[u].emplace_back(v, i);
    adj[v].emplace_back(u, i);
  }
  vector<pii> max_edges, min_edges;
  vector<vector<pii>> paths;
  {
    FU fu_max(n + 2);
    for (auto [a, b] : order) {
      if (!fu_max.Union(a, b)) {
        max_edges.emplace_back(min(a, b), max(a, b));
      }
    }
  }
  reverse((order).begin(), (order).end());
  {
    FU fu_min(n + 2);
    int idx = 0;
    for (auto [a, b] : order) {
      if (!fu_min.Union(a, b)) {
        min_edges.emplace_back(a, b);
      } else {
        tree[a].emplace_back(b, idx);
        tree[b].emplace_back(a, idx);
      }
      ++idx;
    }
  }
  Dfs(1, -1);
  for (int i = 0; i < ((int)(min_edges).size()); ++i) {
    paths.push_back(Path(min_edges[i].first, min_edges[i].second));
  }
  debug() << " ["
          << "max_edges"
             ": "
          << (max_edges) << "] "
          << " ["
          << "min_edges"
             ": "
          << (min_edges) << "] "
          << " ["
          << "paths"
             ": "
          << (paths) << "] ";
  for (int i = 1; i <= n; ++i) {
    num_reach[i] = 1;
  }
  map<pii, int> cnts;
  FU fu_add(n + 2);
  int idx = 0;
  for (auto [a, b] : order) {
    debug() << " ["
            << "a"
               ": "
            << (a) << "] "
            << " ["
            << "b"
               ": "
            << (b) << "] ";
    int x = num_reach[a], y = num_reach[b];
    num_reach[a] += y;
    num_reach[b] += x;
    if (fu_add.Union(a, b)) {
      cnts[pii(a, b)] = x + y;
      cnts[pii(b, a)] = x + y;
    } else {
      debug() << range(num_reach + 1, num_reach + n + 1) << " ["
              << "a"
                 ": "
              << (a) << "] "
              << " ["
              << "b"
                 ": "
              << (b) << "] ";
      auto path = paths[idx];
      debug() << " ["
              << "path"
                 ": "
              << (path) << "] ";
      const int s = ((int)(path).size());
      int num_top = 0;
      int xx = -1, yy = -1;
      for (int i = 0; i < s; ++i) {
        int left = i ? path[i - 1].second : (int)1e9;
        int right = i < s - 1 ? path[i + 1].second : (int)1e9;
        if (path[i].second < left && path[i].second < right) {
          ++num_top;
          xx = path[i].first;
          yy = i ? path[i - 1].first : a;
        }
      }
      if (num_top == 1) {
        debug() << " ["
                << "xx"
                   ": "
                << (xx) << "] "
                << " ["
                << "yy"
                   ": "
                << (yy) << "] ";
        num_reach[a] -= cnts[pii(xx, yy)];
        num_reach[b] -= cnts[pii(yy, xx)];
      }
      ++idx;
    }
    debug() << range(num_reach + 1, num_reach + n + 1);
  }
  for (int i = 1; i <= n; ++i) {
    cout << num_reach[i] - 1 << " ";
  }
  cout << "\n";
}

### 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("O3")
using namespace std;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c* x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  template <class c>
  debug& operator<<(const c&) {
    return *this;
  }
};
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
const int kMaxN = 7e5;
struct FU {
  vi parent;
  FU(int n) : parent(n) { iota((parent).begin(), (parent).end(), 0); }
  int Find(int v) {
    if (parent[v] == v) {
      return v;
    }
    return parent[v] = Find(parent[v]);
  }
  bool Union(int u, int v) {
    u = Find(u);
    v = Find(v);
    if (u != v) {
      parent[u] = v;
      return true;
    }
    return false;
  }
};
int num_reach[kMaxN];
vector<pii> adj[kMaxN];
int n, m;
vector<pii> tree[kMaxN];
int pre[kMaxN], post[kMaxN], ctm;
pii pnt[kMaxN];
void Dfs(int v, int p) {
  debug() << "Dfs "
          << " ["
          << "v"
             ": "
          << (v) << "] "
          << " ["
          << "p"
             ": "
          << (p) << "] ";
  pre[v] = ctm++;
  for (auto& edge : tree[v]) {
    int s = edge.first;
    if (s == p) {
      continue;
    }
    pnt[s] = pii(v, edge.second);
    Dfs(s, v);
  }
  post[v] = ctm;
}
bool Par(int p, int v) { return pre[p] <= pre[v] && post[v] <= post[p]; }
vector<pii> Path(int a, int b) {
  debug() << "Path "
          << " ["
          << "a"
             ": "
          << (a) << "] "
          << " ["
          << "b"
             ": "
          << (b) << "] ";
  vector<pii> xxx, suf;
  while (!Par(a, b) && !Par(b, a)) {
    debug() << " ["
            << "a"
               ": "
            << (a) << "] "
            << " ["
            << "b"
               ": "
            << (b) << "] "
            << " ["
            << "pnt[a]"
               ": "
            << (pnt[a]) << "] ";
    xxx.push_back(pnt[a]);
    a = pnt[a].first;
  }
  while (!Par(a, b)) {
    xxx.push_back(pnt[a]);
    a = pnt[a].first;
  }
  while (!Par(b, a)) {
    suf.push_back(pii(b, pnt[b].second));
    b = pnt[b].first;
  }
  reverse((suf).begin(), (suf).end());
  for (auto x : suf) xxx.push_back(x);
  return xxx;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
  cin >> n >> m;
  vector<pii> order;
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    order.emplace_back(u, v);
    adj[u].emplace_back(v, i);
    adj[v].emplace_back(u, i);
  }
  vector<pii> max_edges, min_edges;
  vector<vector<pii>> paths;
  {
    FU fu_max(n + 2);
    for (auto [a, b] : order) {
      if (!fu_max.Union(a, b)) {
        max_edges.emplace_back(min(a, b), max(a, b));
      }
    }
  }
  reverse((order).begin(), (order).end());
  {
    FU fu_min(n + 2);
    int idx = 0;
    for (auto [a, b] : order) {
      if (!fu_min.Union(a, b)) {
        min_edges.emplace_back(a, b);
      } else {
        tree[a].emplace_back(b, idx);
        tree[b].emplace_back(a, idx);
      }
      ++idx;
    }
  }
  Dfs(1, -1);
  for (int i = 0; i < ((int)(min_edges).size()); ++i) {
    paths.push_back(Path(min_edges[i].first, min_edges[i].second));
  }
  debug() << " ["
          << "max_edges"
             ": "
          << (max_edges) << "] "
          << " ["
          << "min_edges"
             ": "
          << (min_edges) << "] "
          << " ["
          << "paths"
             ": "
          << (paths) << "] ";
  for (int i = 1; i <= n; ++i) {
    num_reach[i] = 1;
  }
  map<pii, int> cnts;
  FU fu_add(n + 2);
  int idx = 0;
  for (auto [a, b] : order) {
    debug() << " ["
            << "a"
               ": "
            << (a) << "] "
            << " ["
            << "b"
               ": "
            << (b) << "] ";
    int x = num_reach[a], y = num_reach[b];
    num_reach[a] += y;
    num_reach[b] += x;
    if (fu_add.Union(a, b)) {
      cnts[pii(a, b)] = x + y;
      cnts[pii(b, a)] = x + y;
    } else {
      debug() << range(num_reach + 1, num_reach + n + 1) << " ["
              << "a"
                 ": "
              << (a) << "] "
              << " ["
              << "b"
                 ": "
              << (b) << "] ";
      auto path = paths[idx];
      debug() << " ["
              << "path"
                 ": "
              << (path) << "] ";
      const int s = ((int)(path).size());
      int num_top = 0;
      int xx = -1, yy = -1;
      for (int i = 0; i < s; ++i) {
        int left = i ? path[i - 1].second : (int)1e9;
        int right = i < s - 1 ? path[i + 1].second : (int)1e9;
        if (path[i].second < left && path[i].second < right) {
          ++num_top;
          xx = path[i].first;
          yy = i ? path[i - 1].first : a;
        }
      }
      if (num_top == 1) {
        debug() << " ["
                << "xx"
                   ": "
                << (xx) << "] "
                << " ["
                << "yy"
                   ": "
                << (yy) << "] ";
        num_reach[a] -= cnts[pii(xx, yy)];
        num_reach[b] -= cnts[pii(yy, xx)];
      }
      ++idx;
    }
    debug() << range(num_reach + 1, num_reach + n + 1);
  }
  for (int i = 1; i <= n; ++i) {
    cout << num_reach[i] - 1 << " ";
  }
  cout << "\n";
}

```