You are given an undirected graph of N nodes and M edges, E_1, E_2, ... E_M.

A connected graph is a cactus if each of it's edges belogs to at most one simple cycle. A graph is a desert if each of it's connected components is a cactus. 

Find the number of pairs (L, R), (1 ≤ L ≤ R ≤ M) such that, if we delete all the edges except for E_L, E_{L+1}, ... E_R, the graph is a desert. 

Input

The first line contains two integers N and M (2 ≤ N ≤ 2.5 × 10^5, 1 ≤ M ≤ 5 × 10^5). Each of the next M lines contains two integers. The i-th line describes the i-th edge. It contains integers U_i and V_i, the nodes connected by the i-th edge (E_i=(U_i, V_i)). It is guaranteed that 1 ≤ U_i, V_i ≤ N and U_i ≠ V_i. 

Output

The output contains one integer number – the answer.

Examples

Input


5 6
1 2
2 3
3 4
4 5
5 1
2 4


Output


20

Input


2 3
1 2
1 2
1 2


Output


5

Note

In the second example: Graphs for pairs (1, 1), (2, 2) and (3, 3) are deserts because they don't have any cycles. Graphs for pairs (1, 2) and (2, 3) have one cycle of length 2 so they are deserts.
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
 4 5
1 2
2 3
2 4
3 4
4 1
 5 4
1 2
2 3
3 4
4 5
 3 6
1 2
2 3
3 1
1 2
2 3
3 1
 10 15
1 2
1 5
1 6
2 3
2 7
3 4
3 8
4 5
4 9
5 10
6 8
6 9
7 9
7 10
8 10
 8 11
1 2
2 3
2 4
3 4
4 1
5 6
6 8
6 7
7 8
7 5
8 5
 5 1
1 2
 5 8
1 2
2 3
3 1
2 5
3 4
4 5
5 3
1 4

38
 14
 10
 15
 99
 48
 1
 30

#include <bits/stdc++.h>
long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = x * 10 + (c - '0'), c = getchar();
  return f * x;
}
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
template <typename T>
bool umin(T& a, T t) {
  if (a > t) return a = t, 1;
  return 0;
}
template <typename T>
bool umax(T& a, T t) {
  if (a < t) return a = t, 1;
  return 0;
}
const int MAXN = 1500011, INF = 1e9 + 233;
bool used[MAXN];
namespace LCT {
int fa[MAXN], son[MAXN][2], val[MAXN], mx[MAXN], tag[MAXN], T[MAXN], minT[MAXN];
bool rev[MAXN];
bool not_root(int x) { return son[fa[x]][0] == x || son[fa[x]][1] == x; }
void pushup(int x) {
  mx[x] = max(max(val[x], mx[son[x][0]]), mx[son[x][1]]),
  minT[x] = min(min(T[x], minT[son[x][0]]), minT[son[x][1]]);
}
void pushdown(int x) {
  int &l = son[x][0], &r = son[x][1];
  if (rev[x]) std::swap(l, r), rev[l] ^= 1, rev[r] ^= 1, rev[x] = 0;
  if (tag[x] && l) val[l] += tag[x], mx[l] += tag[x], tag[l] += tag[x];
  if (tag[x] && r) val[r] += tag[x], mx[r] += tag[x], tag[r] += tag[x];
  tag[x] = 0;
}
void rotate(int x) {
  int y = fa[x], z = fa[y], k = (son[y][1] == x);
  if (not_root(y)) son[z][son[z][1] == y] = x;
  fa[x] = z;
  son[y][k] = son[x][!k], fa[son[x][!k]] = y;
  son[x][!k] = y, fa[y] = x;
  pushup(y), pushup(x);
}
int s[MAXN];
void splay(int x) {
  int top = 0;
  s[++top] = x;
  for (int y = x; not_root(y); y = fa[y]) s[++top] = fa[y];
  while (top) pushdown(s[top--]);
  while (not_root(x)) {
    int y = fa[x];
    if (not_root(y)) rotate((son[y][1] == x) == (son[fa[y]][1] == y) ? y : x);
    rotate(x);
  }
  pushup(x);
}
void access(int x) {
  for (int y = 0; x; y = x, x = fa[x]) splay(x), son[x][1] = y, pushup(x);
}
void make_root(int x) { access(x), splay(x), rev[x] ^= 1; }
void link(int x, int y) { make_root(x), fa[x] = y; }
void split(int x, int y) { make_root(x), access(y), splay(y); }
int get_root(int x) {
  access(x), splay(x);
  while (son[x][0]) x = son[x][0];
  return x;
}
int Qmax(int x, int y) {
  if (get_root(x) != get_root(y)) return -INF;
  split(x, y);
  return mx[y];
}
void Add(int x, int y, int k) {
  split(x, y), val[y] += k, mx[y] += k, tag[y] += k;
}
int Find(int x, int k) {
  if (T[x] == k) return x;
  if (minT[son[x][0]] == k) return Find(son[x][0], k);
  return Find(son[x][1], k);
}
int replace(int x, int y, int k) {
  if (get_root(x) != get_root(y)) {
    T[k] = k, used[k] = 1;
    link(x, k), link(y, k);
    splay(k);
    return 0;
  }
  split(x, y);
  int p = minT[y];
  splay(p), fa[son[p][0]] = fa[son[p][1]] = 0, son[p][0] = son[p][1] = 0;
  used[p] = 0, used[k] = 1, T[k] = k;
  link(x, k), link(y, k);
  return p;
}
void cut(int x, int y) {
  split(x, y);
  fa[x] = 0, son[y][0] = 0, pushup(y);
}
}  // namespace LCT
std::pair<int, int> ed[MAXN];
int main() {
  int n = read(), m = read();
  for (int i = 1; i <= m; ++i) ed[i].first = read(), ed[i].second = read();
  for (int i = 0; i <= n; ++i)
    LCT::T[i] = INF, LCT::minT[i] = INF, LCT::val[i] = -INF, LCT::mx[i] = -INF;
  long long ans = 0;
  int r = 1;
  for (int l = 1; l <= m; ++l) {
    while (r <= m && LCT::Qmax(ed[r].first, ed[r].second) <= 0) {
      int p = LCT::replace(ed[r].first, ed[r].second, n + r);
      if (p) LCT::Add(ed[p - n].first, ed[p - n].second, 1);
      ++r;
    }
    ans += r - l;
    if (used[n + l]) {
      LCT::cut(ed[l].first, n + l), LCT::cut(ed[l].second, n + l);
    } else
      LCT::Add(ed[l].first, ed[l].second, -1);
  }
  printf("%lld\n", ans);
  return 0;
}
