#include <bits/stdc++.h>
using namespace std;
template <typename T>
void maxtt(T& t1, T t2) {
  t1 = max(t1, t2);
}
template <typename T>
void mintt(T& t1, T t2) {
  t1 = min(t1, t2);
}
bool debug = 0;
int n, m, k;
string direc = "URDL";
const long long MOD2 = (long long)998244353 * (long long)998244353;
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int& x, int y, int mod = 998244353) {
  x += y;
  if (x >= mod) x -= mod;
  if (x < 0) x += mod;
  assert(x >= 0 && x < mod);
}
void et(int x = -1) {
  printf("%d\n", x);
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 998244353) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) { return y ? gcd1(y, x % y) : x; }
vector<int> mp[500135];
int lev[500135], N;
int cutid[500135], bcc[500135], ccnt, bcnt;
vector<int> vb[500135];
stack<int> s;
int tarjan(int x, int f, int l) {
  int low;
  lev[x] = low = l;
  s.push(x);
  int iscut = 0, son = 0;
  for (auto i : mp[x])
    if (i != f) {
      if (lev[i] != -1) {
        low = min(low, lev[i]);
        continue;
      }
      son++;
      int tmp = tarjan(i, x, l + 1);
      low = min(low, tmp);
      if (tmp >= l) {
        iscut = 1;
        bcnt++;
        int top;
        do {
          bcc[top = s.top()] = bcnt;
          vb[bcnt].push_back(top);
          s.pop();
        } while (top != i);
        bcc[x] = bcnt;
        vb[bcnt].push_back(x);
      }
    }
  if ((x != f && iscut) || (x == f && son > 1)) cutid[x] = ++ccnt;
  return low;
}
int u[500135], v[500135], rel[500135];
void init() {
  map<pair<int, int>, int> mp;
  for (int(i) = 1; (i) <= (int)(m); (i)++) {
    mp[{u[i], v[i]}] = i;
    mp[{v[i], u[i]}] = i;
  }
  memset(lev, -1, sizeof lev);
  tarjan(1, 0, 0);
  for (int(i) = 1; (i) <= (int)(bcnt); (i)++)
    if (vb[i].size() > 2) {
      vector<int> es;
      int N = vb[i].size();
      int mi = (1 << 30), mx = 0;
      for (int(j) = 0; (j) < (int)(N); (j)++) {
        int k = (j + 1) % N;
        es.push_back(mp[{vb[i][j], vb[i][k]}]);
        mintt(mi, es.back());
        maxtt(mx, es.back());
      }
      N = es.size();
      int st = 0;
      while (es[st] != mi) st++;
      bool fg = 1;
      for (int j = st + 1;; j++) {
        if (es[j % N] < es[(j + N - 1) % N]) {
          if (es[(j + N - 1) % N] != mx) fg = 0;
          break;
        }
      }
      for (int j = st - 1;; j--) {
        if (es[(j + N) % N] < es[(j + 1 + N) % N]) {
          if (es[(j + N + 1) % N] != mx) fg = 0;
          break;
        }
      }
      if (fg)
        rel[mi] = mx;
      else
        rel[mi] = -1;
    }
}
long long dp[500135], dpe[500135];
void fmain(int tid) {
  scanf("%d%d", &n, &m);
  for (int(i) = 1; (i) <= (int)(m); (i)++) {
    scanf("%d%d", u + i, v + i);
    mp[u[i]].push_back(v[i]);
    mp[v[i]].push_back(u[i]);
  }
  init();
  for (int(i) = 1; (i) <= (int)(n); (i)++) dp[i] = 1;
  for (int i = m; i; i--) {
    long long tt = dp[u[i]] + dp[v[i]];
    if (rel[i] > 0) {
      tt -= dpe[rel[i]];
    }
    dpe[i] = tt;
    dp[u[i]] = dp[v[i]] = tt;
  }
  for (int(i) = 1; (i) <= (int)(n); (i)++) printf("%lld ", dp[i] - 1);
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}

### 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 <typename T>
void maxtt(T& t1, T t2) {
  t1 = max(t1, t2);
}
template <typename T>
void mintt(T& t1, T t2) {
  t1 = min(t1, t2);
}
bool debug = 0;
int n, m, k;
string direc = "URDL";
const long long MOD2 = (long long)998244353 * (long long)998244353;
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int& x, int y, int mod = 998244353) {
  x += y;
  if (x >= mod) x -= mod;
  if (x < 0) x += mod;
  assert(x >= 0 && x < mod);
}
void et(int x = -1) {
  printf("%d\n", x);
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 998244353) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) { return y ? gcd1(y, x % y) : x; }
vector<int> mp[500135];
int lev[500135], N;
int cutid[500135], bcc[500135], ccnt, bcnt;
vector<int> vb[500135];
stack<int> s;
int tarjan(int x, int f, int l) {
  int low;
  lev[x] = low = l;
  s.push(x);
  int iscut = 0, son = 0;
  for (auto i : mp[x])
    if (i != f) {
      if (lev[i] != -1) {
        low = min(low, lev[i]);
        continue;
      }
      son++;
      int tmp = tarjan(i, x, l + 1);
      low = min(low, tmp);
      if (tmp >= l) {
        iscut = 1;
        bcnt++;
        int top;
        do {
          bcc[top = s.top()] = bcnt;
          vb[bcnt].push_back(top);
          s.pop();
        } while (top != i);
        bcc[x] = bcnt;
        vb[bcnt].push_back(x);
      }
    }
  if ((x != f && iscut) || (x == f && son > 1)) cutid[x] = ++ccnt;
  return low;
}
int u[500135], v[500135], rel[500135];
void init() {
  map<pair<int, int>, int> mp;
  for (int(i) = 1; (i) <= (int)(m); (i)++) {
    mp[{u[i], v[i]}] = i;
    mp[{v[i], u[i]}] = i;
  }
  memset(lev, -1, sizeof lev);
  tarjan(1, 0, 0);
  for (int(i) = 1; (i) <= (int)(bcnt); (i)++)
    if (vb[i].size() > 2) {
      vector<int> es;
      int N = vb[i].size();
      int mi = (1 << 30), mx = 0;
      for (int(j) = 0; (j) < (int)(N); (j)++) {
        int k = (j + 1) % N;
        es.push_back(mp[{vb[i][j], vb[i][k]}]);
        mintt(mi, es.back());
        maxtt(mx, es.back());
      }
      N = es.size();
      int st = 0;
      while (es[st] != mi) st++;
      bool fg = 1;
      for (int j = st + 1;; j++) {
        if (es[j % N] < es[(j + N - 1) % N]) {
          if (es[(j + N - 1) % N] != mx) fg = 0;
          break;
        }
      }
      for (int j = st - 1;; j--) {
        if (es[(j + N) % N] < es[(j + 1 + N) % N]) {
          if (es[(j + N + 1) % N] != mx) fg = 0;
          break;
        }
      }
      if (fg)
        rel[mi] = mx;
      else
        rel[mi] = -1;
    }
}
long long dp[500135], dpe[500135];
void fmain(int tid) {
  scanf("%d%d", &n, &m);
  for (int(i) = 1; (i) <= (int)(m); (i)++) {
    scanf("%d%d", u + i, v + i);
    mp[u[i]].push_back(v[i]);
    mp[v[i]].push_back(u[i]);
  }
  init();
  for (int(i) = 1; (i) <= (int)(n); (i)++) dp[i] = 1;
  for (int i = m; i; i--) {
    long long tt = dp[u[i]] + dp[v[i]];
    if (rel[i] > 0) {
      tt -= dpe[rel[i]];
    }
    dpe[i] = tt;
    dp[u[i]] = dp[v[i]] = tt;
  }
  for (int(i) = 1; (i) <= (int)(n); (i)++) printf("%lld ", dp[i] - 1);
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}

```