#include <bits/stdc++.h>
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;
  }
};
const int MAX_N = 5e5 + 5;
vector<pair<int, int>> edges[MAX_N];
bool visited[MAX_N];
pair<int, int> parent[MAX_N];
int depth[MAX_N];
vector<int> smallest;
vector<int> find_path(int a, int b) {
  assert(visited[a] && visited[b]);
  vector<int> left, right;
  while (a != b) {
    if (depth[a] > depth[b]) {
      left.push_back(parent[a].second);
      a = parent[a].first;
    } else {
      right.push_back(parent[b].second);
      b = parent[b].first;
    }
  }
  reverse(right.begin(), right.end());
  for (int x : right) {
    left.push_back(x);
  }
  return left;
}
void dfs(int a) {
  assert(!visited[a]);
  visited[a] = true;
  for (pair<int, int> e : edges[a]) {
    int b = e.first;
    int id = e.second;
    if (b == parent[a].first) {
      continue;
    }
    if (!visited[b]) {
      depth[b] = depth[a] + 1;
      parent[b] = {a, id};
      dfs(b);
    } else {
      vector<int> cycle = find_path(a, b);
      cycle.push_back(id);
      int s = cycle.size();
      assert(s >= 3);
      debug() << " ["
              << "a"
                 ": "
              << (a)
              << "] "
                 " ["
              << "b"
                 ": "
              << (b)
              << "] "
                 " ["
              << "cycle"
                 ": "
              << (cycle) << "] ";
      int ws = 0, wb = 0;
      for (int i = 0; i < s; ++i) {
        if (cycle[i] < cycle[ws]) {
          ws = i;
        }
        if (cycle[i] > cycle[wb]) {
          wb = i;
        }
      }
      bool ok = true;
      for (int i = ws; i != wb; i = (i + 1) % s) {
        if (cycle[i] > cycle[(i + 1) % s]) {
          ok = false;
        }
      }
      for (int i = wb; i != ws; i = (i + 1) % s) {
        if (cycle[i] < cycle[(i + 1) % s]) {
          ok = false;
        }
      }
      if (ok) {
        smallest[cycle[wb]] = cycle[ws];
      }
    }
  }
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  smallest.resize(m, -1);
  vector<pair<int, int>> order(m);
  for (int i = 0; i < m; ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a;
    --b;
    int j = m - 1 - i;
    edges[a].emplace_back(b, j);
    edges[b].emplace_back(a, j);
    order[j] = {a, b};
  }
  dfs(0);
  vector<int> sum(n, 1);
  vector<int> memo(m);
  for (int id = 0; id < m; ++id) {
    int a = order[id].first;
    int b = order[id].second;
    int together = sum[a] + sum[b];
    if (smallest[id] != -1) {
      together -= memo[smallest[id]];
    }
    memo[id] = together;
    sum[a] = sum[b] = together;
  }
  for (int x : sum) {
    printf("%d ", x - 1);
  }
  puts("");
}

### Prompt

In cpp, your task is to solve 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 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;
  }
};
const int MAX_N = 5e5 + 5;
vector<pair<int, int>> edges[MAX_N];
bool visited[MAX_N];
pair<int, int> parent[MAX_N];
int depth[MAX_N];
vector<int> smallest;
vector<int> find_path(int a, int b) {
  assert(visited[a] && visited[b]);
  vector<int> left, right;
  while (a != b) {
    if (depth[a] > depth[b]) {
      left.push_back(parent[a].second);
      a = parent[a].first;
    } else {
      right.push_back(parent[b].second);
      b = parent[b].first;
    }
  }
  reverse(right.begin(), right.end());
  for (int x : right) {
    left.push_back(x);
  }
  return left;
}
void dfs(int a) {
  assert(!visited[a]);
  visited[a] = true;
  for (pair<int, int> e : edges[a]) {
    int b = e.first;
    int id = e.second;
    if (b == parent[a].first) {
      continue;
    }
    if (!visited[b]) {
      depth[b] = depth[a] + 1;
      parent[b] = {a, id};
      dfs(b);
    } else {
      vector<int> cycle = find_path(a, b);
      cycle.push_back(id);
      int s = cycle.size();
      assert(s >= 3);
      debug() << " ["
              << "a"
                 ": "
              << (a)
              << "] "
                 " ["
              << "b"
                 ": "
              << (b)
              << "] "
                 " ["
              << "cycle"
                 ": "
              << (cycle) << "] ";
      int ws = 0, wb = 0;
      for (int i = 0; i < s; ++i) {
        if (cycle[i] < cycle[ws]) {
          ws = i;
        }
        if (cycle[i] > cycle[wb]) {
          wb = i;
        }
      }
      bool ok = true;
      for (int i = ws; i != wb; i = (i + 1) % s) {
        if (cycle[i] > cycle[(i + 1) % s]) {
          ok = false;
        }
      }
      for (int i = wb; i != ws; i = (i + 1) % s) {
        if (cycle[i] < cycle[(i + 1) % s]) {
          ok = false;
        }
      }
      if (ok) {
        smallest[cycle[wb]] = cycle[ws];
      }
    }
  }
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  smallest.resize(m, -1);
  vector<pair<int, int>> order(m);
  for (int i = 0; i < m; ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a;
    --b;
    int j = m - 1 - i;
    edges[a].emplace_back(b, j);
    edges[b].emplace_back(a, j);
    order[j] = {a, b};
  }
  dfs(0);
  vector<int> sum(n, 1);
  vector<int> memo(m);
  for (int id = 0; id < m; ++id) {
    int a = order[id].first;
    int b = order[id].second;
    int together = sum[a] + sum[b];
    if (smallest[id] != -1) {
      together -= memo[smallest[id]];
    }
    memo[id] = together;
    sum[a] = sum[b] = together;
  }
  for (int x : sum) {
    printf("%d ", x - 1);
  }
  puts("");
}

```