#include <bits/stdc++.h>
using namespace std;
template <typename T>
using maxHeap = priority_queue<T, vector<T>, less<T>>;
template <typename T>
using minHeap = priority_queue<T, vector<T>, greater<T>>;
template <typename Iter>
ostream& _out(ostream& s, Iter b, Iter e) {
  s << "[";
  for (auto it = b; it != e; it++) s << (it == b ? "" : " ") << *it;
  s << "]";
  return s;
}
template <typename A, typename B>
ostream& operator<<(ostream& s, const pair<A, B>& p) {
  return s << "(" << p.first << "," << p.second << ")";
}
template <typename T>
ostream& operator<<(ostream& s, const vector<T>& c) {
  return _out(s, begin(c), end(c));
}
bool debug = 0;
template <typename T>
void DEBUG(const T& x) {
  if (debug) cerr << x;
}
template <typename T, typename... Args>
void DEBUG(const T& head, const Args&... tail) {
  if (debug) {
    cerr << head;
    DEBUG(tail...);
  }
}
const int N = 300000 + 5;
class BCC {
 private:
  int n, m, cnt, bcnt;
  vector<vector<pair<int, int>>> G;
  vector<int> low, dfn, ids, sz;
  stack<int> stk;
  void dfs(int w, int f) {
    dfn[w] = cnt++;
    low[w] = dfn[w];
    for (auto i : G[w]) {
      int u = i.first, t = i.second;
      if (u == f) continue;
      if (dfn[u] == -1) {
        stk.push(t);
        dfs(u, w);
        if (low[u] >= dfn[w]) {
          while (stk.top() != t) {
            assert(!stk.empty());
            ids[stk.top()] = bcnt;
            sz[bcnt]++;
            stk.pop();
          }
          ids[stk.top()] = bcnt;
          sz[bcnt]++;
          stk.pop();
          bcnt++;
        }
        low[w] = min(low[w], low[u]);
      } else {
        if (dfn[u] < dfn[w]) stk.push(t);
        low[w] = min(low[w], dfn[u]);
      }
    }
  }

 public:
  void init(int n_, int m_) {
    n = n_, m = m_, cnt = 0;
    G.resize(n);
    fill(begin(G), end(G), vector<pair<int, int>>());
    low.resize(n);
    dfn.resize(n);
    fill(begin(dfn), end(dfn), -1);
    ids.resize(m);
    sz.resize(m);
  }
  void add_edge(int u, int v) {
    assert(0 <= u and u < n);
    assert(0 <= v and v < n);
    G[u].push_back({v, cnt});
    G[v].push_back({u, cnt});
    cnt++;
  }
  void solve() {
    assert(cnt == m);
    cnt = 1, bcnt = 0;
    for (int i = 0; i < n; i++) {
      if (dfn[i] != -1) continue;
      while (!stk.empty()) stk.pop();
      dfs(i, i);
    }
  }
  int count() { return bcnt; }
  int get_id(int t) { return ids[t]; }
  int get_size(int x) { return sz[x]; }
} bcc;
pair<int, int> egs[N], line[N];
int r[N];
long long preR[N];
int main(int argc, char* argv[]) {
  if (argc > 1 and string(argv[1]) == "-D") debug = 1;
  if (!debug) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
  }
  int n, m;
  cin >> n >> m;
  bcc.init(n, m);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    bcc.add_edge(u - 1, v - 1);
    egs[i] = {u, v};
  }
  bcc.solve();
  for (int i = 1; i <= bcc.count(); i++) line[i] = {n, -1};
  for (int i = 0; i < m; i++) {
    int id = bcc.get_id(i) + 1;
    DEBUG(egs[i], " : ", id, '\n');
    if (debug)
      cerr << __PRETTY_FUNCTION__ << ":" << 148 << " - "
           << "bcc.get_size(id - 1)"
           << "=" << bcc.get_size(id - 1) << '\n';
    if (bcc.get_size(id - 1) == 1) continue;
    line[id].first = min({egs[i].first, egs[i].second, line[id].first});
    line[id].second = max({egs[i].first, egs[i].second, line[id].second});
  }
  fill_n(r + 1, n, n + 1);
  for (int i = 1; i <= bcc.count(); i++) {
    if (bcc.get_size(i - 1) == 1) continue;
    r[line[i].first] = min(line[i].second, r[line[i].first]);
    DEBUG("r[", line[i].first, "]=", r[line[i].first], '\n');
  }
  int rr = n + 1;
  for (int i = n; i >= 1; i--) {
    rr = min(r[i], rr);
    r[i] = rr;
  }
  for (int i = 1; i <= n; i++) DEBUG(r[i], " \n"[i == n]);
  for (int i = 1; i <= n; i++) preR[i] = preR[i - 1] + r[i];
  auto sumr = [](int ql, int qr) { return preR[qr] - preR[ql]; };
  int q;
  cin >> q;
  while (q--) {
    long long ql, qr;
    cin >> ql >> qr;
    ql--;
    long long ans = sumr(ql, qr) - (ql + qr + 1) * (qr - ql) / 2;
    int idx = distance(r, upper_bound(r + ql + 1, r + n + 1, qr));
    if (idx <= qr) ans -= sumr(idx - 1, qr) - (qr + 1) * (qr - idx + 1);
    cout << ans << '\n';
  }
  return 0;
}

### Prompt

Please formulate a cpp solution to the following problem:

You are given an undirected graph with n vertices. There are no edge-simple cycles with the even length in it. In other words, there are no cycles of even length that pass each edge at most once. Let's enumerate vertices from 1 to n. 

You have to answer q queries. Each query is described by a segment of vertices [l; r], and you have to count the number of its subsegments [x; y] (l ≤ x ≤ y ≤ r), such that if we delete all vertices except the segment of vertices [x; y] (including x and y) and edges between them, the resulting graph is bipartite.

Input

The first line contains two integers n and m (1 ≤ n ≤ 3·105, 1 ≤ m ≤ 3·105) — the number of vertices and the number of edges in the graph.

The next m lines describe edges in the graph. The i-th of these lines contains two integers ai and bi (1 ≤ ai, bi ≤ n; ai ≠ bi), denoting an edge between vertices ai and bi. It is guaranteed that this graph does not contain edge-simple cycles of even length.

The next line contains a single integer q (1 ≤ q ≤ 3·105) — the number of queries.

The next q lines contain queries. The i-th of these lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n) — the query parameters.

Output

Print q numbers, each in new line: the i-th of them should be the number of subsegments [x; y] (li ≤ x ≤ y ≤ ri), such that the graph that only includes vertices from segment [x; y] and edges between them is bipartite.

Examples

Input

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


Output

5
5
14


Input

8 9
1 2
2 3
3 1
4 5
5 6
6 7
7 8
8 4
7 2
3
1 8
1 4
3 8


Output

27
8
19

Note

The first example is shown on the picture below:

<image>

For the first query, all subsegments of [1; 3], except this segment itself, are suitable.

For the first query, all subsegments of [4; 6], except this segment itself, are suitable.

For the third query, all subsegments of [1; 6] are suitable, except [1; 3], [1; 4], [1; 5], [1; 6], [2; 6], [3; 6], [4; 6].

The second example is shown on the picture below:

<image>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using maxHeap = priority_queue<T, vector<T>, less<T>>;
template <typename T>
using minHeap = priority_queue<T, vector<T>, greater<T>>;
template <typename Iter>
ostream& _out(ostream& s, Iter b, Iter e) {
  s << "[";
  for (auto it = b; it != e; it++) s << (it == b ? "" : " ") << *it;
  s << "]";
  return s;
}
template <typename A, typename B>
ostream& operator<<(ostream& s, const pair<A, B>& p) {
  return s << "(" << p.first << "," << p.second << ")";
}
template <typename T>
ostream& operator<<(ostream& s, const vector<T>& c) {
  return _out(s, begin(c), end(c));
}
bool debug = 0;
template <typename T>
void DEBUG(const T& x) {
  if (debug) cerr << x;
}
template <typename T, typename... Args>
void DEBUG(const T& head, const Args&... tail) {
  if (debug) {
    cerr << head;
    DEBUG(tail...);
  }
}
const int N = 300000 + 5;
class BCC {
 private:
  int n, m, cnt, bcnt;
  vector<vector<pair<int, int>>> G;
  vector<int> low, dfn, ids, sz;
  stack<int> stk;
  void dfs(int w, int f) {
    dfn[w] = cnt++;
    low[w] = dfn[w];
    for (auto i : G[w]) {
      int u = i.first, t = i.second;
      if (u == f) continue;
      if (dfn[u] == -1) {
        stk.push(t);
        dfs(u, w);
        if (low[u] >= dfn[w]) {
          while (stk.top() != t) {
            assert(!stk.empty());
            ids[stk.top()] = bcnt;
            sz[bcnt]++;
            stk.pop();
          }
          ids[stk.top()] = bcnt;
          sz[bcnt]++;
          stk.pop();
          bcnt++;
        }
        low[w] = min(low[w], low[u]);
      } else {
        if (dfn[u] < dfn[w]) stk.push(t);
        low[w] = min(low[w], dfn[u]);
      }
    }
  }

 public:
  void init(int n_, int m_) {
    n = n_, m = m_, cnt = 0;
    G.resize(n);
    fill(begin(G), end(G), vector<pair<int, int>>());
    low.resize(n);
    dfn.resize(n);
    fill(begin(dfn), end(dfn), -1);
    ids.resize(m);
    sz.resize(m);
  }
  void add_edge(int u, int v) {
    assert(0 <= u and u < n);
    assert(0 <= v and v < n);
    G[u].push_back({v, cnt});
    G[v].push_back({u, cnt});
    cnt++;
  }
  void solve() {
    assert(cnt == m);
    cnt = 1, bcnt = 0;
    for (int i = 0; i < n; i++) {
      if (dfn[i] != -1) continue;
      while (!stk.empty()) stk.pop();
      dfs(i, i);
    }
  }
  int count() { return bcnt; }
  int get_id(int t) { return ids[t]; }
  int get_size(int x) { return sz[x]; }
} bcc;
pair<int, int> egs[N], line[N];
int r[N];
long long preR[N];
int main(int argc, char* argv[]) {
  if (argc > 1 and string(argv[1]) == "-D") debug = 1;
  if (!debug) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
  }
  int n, m;
  cin >> n >> m;
  bcc.init(n, m);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    bcc.add_edge(u - 1, v - 1);
    egs[i] = {u, v};
  }
  bcc.solve();
  for (int i = 1; i <= bcc.count(); i++) line[i] = {n, -1};
  for (int i = 0; i < m; i++) {
    int id = bcc.get_id(i) + 1;
    DEBUG(egs[i], " : ", id, '\n');
    if (debug)
      cerr << __PRETTY_FUNCTION__ << ":" << 148 << " - "
           << "bcc.get_size(id - 1)"
           << "=" << bcc.get_size(id - 1) << '\n';
    if (bcc.get_size(id - 1) == 1) continue;
    line[id].first = min({egs[i].first, egs[i].second, line[id].first});
    line[id].second = max({egs[i].first, egs[i].second, line[id].second});
  }
  fill_n(r + 1, n, n + 1);
  for (int i = 1; i <= bcc.count(); i++) {
    if (bcc.get_size(i - 1) == 1) continue;
    r[line[i].first] = min(line[i].second, r[line[i].first]);
    DEBUG("r[", line[i].first, "]=", r[line[i].first], '\n');
  }
  int rr = n + 1;
  for (int i = n; i >= 1; i--) {
    rr = min(r[i], rr);
    r[i] = rr;
  }
  for (int i = 1; i <= n; i++) DEBUG(r[i], " \n"[i == n]);
  for (int i = 1; i <= n; i++) preR[i] = preR[i - 1] + r[i];
  auto sumr = [](int ql, int qr) { return preR[qr] - preR[ql]; };
  int q;
  cin >> q;
  while (q--) {
    long long ql, qr;
    cin >> ql >> qr;
    ql--;
    long long ans = sumr(ql, qr) - (ql + qr + 1) * (qr - ql) / 2;
    int idx = distance(r, upper_bound(r + ql + 1, r + n + 1, qr));
    if (idx <= qr) ans -= sumr(idx - 1, qr) - (qr + 1) * (qr - idx + 1);
    cout << ans << '\n';
  }
  return 0;
}

```