#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const long long inf = 9.2e18;
const int maxn = 3e5 + 70;
const int INF = 2.1e9;
const int maxm = 1e6 + 70;
const int MOD = 1e9 + 7;
const double eps = 1e-7;
const double PI = acos(-1.0);
int n, m, k, q;
vector<int> G[maxn];
stack<pair<int, int> > S;
int low[maxn][20], high[maxn][20], f[maxn][20];
int r[maxn], d[maxn], sz[maxn], qa[maxn], qb[maxn];
long long pre[maxn];
int vis[maxn], dfs_clock, num;
void dfs(int u, int fa) {
  vis[u] = ++dfs_clock;
  sz[u] = 1;
  d[u] = d[fa] + 1;
  f[u][0] = fa;
  low[u][0] = min(u, fa);
  high[u][0] = max(u, fa);
  for (int i = 1; i < 20; i++) {
    f[u][i] = f[f[u][i - 1]][i - 1];
    low[u][i] = min(low[u][i - 1], low[f[u][i - 1]][i - 1]);
    high[u][i] = max(high[u][i - 1], high[f[u][i - 1]][i - 1]);
    if (f[u][i] == 0) break;
  }
  for (int i = 0; i < G[u].size(); i++) {
    if (G[u][i] != fa) {
      int v = G[u][i];
      if (!vis[v]) {
        dfs(v, u);
        sz[u] += sz[v];
      } else if (vis[v] < vis[u]) {
        int l = INF, h = 0, k = 0;
        while ((1 << (k + 1)) <= d[u]) k++;
        int t = u;
        while (t != v) {
          if (d[f[t][k]] >= d[v]) {
            l = min(l, low[t][k]);
            h = max(h, high[t][k]);
            t = f[t][k];
          }
          k--;
        }
        r[l] = min(r[l], h);
        num++;
      }
    }
  }
}
vector<long long> ans1, ans2;
void solve1() {
  d[0] = -1;
  num = dfs_clock = 0;
  memset(vis, 0, sizeof(vis));
  for (int i = 0; i <= n; i++) r[i] = INF;
  for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
      dfs(i, 0);
    }
  }
  while (!S.empty()) S.pop();
  for (int i = 1; i <= n; i++) {
    if (r[i] != INF) {
      while (!S.empty() && r[i] <= S.top().second) S.pop();
      S.push(make_pair(i, r[i]));
    }
  }
  int b = INF, p = n;
  while (!S.empty()) {
    int x = S.top().first, y = S.top().second;
    S.pop();
    while (p > x) {
      r[p--] = b;
    }
    b = y;
  }
  while (p >= 1) r[p--] = b;
  pre[0] = 0;
  for (int i = 1; i <= n; i++) {
    if (r[i] == INF) break;
    pre[i] = pre[i - 1] + (r[i] - i);
  }
  int m = 0;
  for (int i = 1; i <= n; i++) {
    if (r[i] <= i + 1)
      cout << "error: "
           << "i = " << i << " r[i] = " << r[i] << endl;
    if (r[i] < m)
      cout << "error: "
           << "i = " << i << " r[i] = " << r[i] << " m = " << m << endl;
    m = max(m, r[i]);
  }
  ans1.clear();
  for (int i = 0; i < q; i++) {
    int L = qa[i], R = qb[i], a = qa[i], b = qb[i];
    while (L < R) {
      int M = L + (R - L) / 2;
      if (r[M] <= b)
        L = M + 1;
      else
        R = M;
    }
    long long t = b - L + 1;
    long long ans = t * (t + 1) / 2 + pre[L - 1] - pre[a - 1];
    ans1.push_back(ans);
  }
}
void solve2() {
  d[0] = -1;
  num = dfs_clock = 0;
  memset(vis, 0, sizeof(vis));
  for (int i = 0; i <= n; i++) r[i] = INF;
  for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
      dfs(i, 0);
    }
  }
  while (!S.empty()) S.pop();
  for (int i = 1; i <= n; i++) {
    if (r[i] != INF) {
      if (!S.empty() && r[i] <= S.top().second) S.pop();
      S.push(make_pair(i, r[i]));
    }
  }
  int b = INF, p = n;
  while (!S.empty()) {
    int x = S.top().first, y = S.top().second;
    S.pop();
    while (p > x) {
      r[p--] = b;
    }
    b = y;
  }
  while (p >= 1) r[p--] = b;
  ans2.clear();
  for (int i = 0; i < q; i++) {
    int a = qa[i], b = qb[i];
    long long ans = 0;
    for (int j = a; j <= b; j++) {
      ans += min(b + 1, r[j]) - j;
    }
    ans2.push_back(ans);
  }
}
int main() {
  while (cin >> n >> m) {
    for (int i = 0; i <= n; i++) G[i].clear();
    for (int i = 0; i < m; i++) {
      int u, v;
      scanf("%d%d", &u, &v);
      G[u].push_back(v);
      G[v].push_back(u);
    }
    cin >> q;
    for (int i = 0; i < q; i++) scanf("%d%d", &qa[i], &qb[i]);
    solve1();
    for (int i = 0; i < q; i++) printf("%lld\n", ans1[i]);
  }
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const long long inf = 9.2e18;
const int maxn = 3e5 + 70;
const int INF = 2.1e9;
const int maxm = 1e6 + 70;
const int MOD = 1e9 + 7;
const double eps = 1e-7;
const double PI = acos(-1.0);
int n, m, k, q;
vector<int> G[maxn];
stack<pair<int, int> > S;
int low[maxn][20], high[maxn][20], f[maxn][20];
int r[maxn], d[maxn], sz[maxn], qa[maxn], qb[maxn];
long long pre[maxn];
int vis[maxn], dfs_clock, num;
void dfs(int u, int fa) {
  vis[u] = ++dfs_clock;
  sz[u] = 1;
  d[u] = d[fa] + 1;
  f[u][0] = fa;
  low[u][0] = min(u, fa);
  high[u][0] = max(u, fa);
  for (int i = 1; i < 20; i++) {
    f[u][i] = f[f[u][i - 1]][i - 1];
    low[u][i] = min(low[u][i - 1], low[f[u][i - 1]][i - 1]);
    high[u][i] = max(high[u][i - 1], high[f[u][i - 1]][i - 1]);
    if (f[u][i] == 0) break;
  }
  for (int i = 0; i < G[u].size(); i++) {
    if (G[u][i] != fa) {
      int v = G[u][i];
      if (!vis[v]) {
        dfs(v, u);
        sz[u] += sz[v];
      } else if (vis[v] < vis[u]) {
        int l = INF, h = 0, k = 0;
        while ((1 << (k + 1)) <= d[u]) k++;
        int t = u;
        while (t != v) {
          if (d[f[t][k]] >= d[v]) {
            l = min(l, low[t][k]);
            h = max(h, high[t][k]);
            t = f[t][k];
          }
          k--;
        }
        r[l] = min(r[l], h);
        num++;
      }
    }
  }
}
vector<long long> ans1, ans2;
void solve1() {
  d[0] = -1;
  num = dfs_clock = 0;
  memset(vis, 0, sizeof(vis));
  for (int i = 0; i <= n; i++) r[i] = INF;
  for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
      dfs(i, 0);
    }
  }
  while (!S.empty()) S.pop();
  for (int i = 1; i <= n; i++) {
    if (r[i] != INF) {
      while (!S.empty() && r[i] <= S.top().second) S.pop();
      S.push(make_pair(i, r[i]));
    }
  }
  int b = INF, p = n;
  while (!S.empty()) {
    int x = S.top().first, y = S.top().second;
    S.pop();
    while (p > x) {
      r[p--] = b;
    }
    b = y;
  }
  while (p >= 1) r[p--] = b;
  pre[0] = 0;
  for (int i = 1; i <= n; i++) {
    if (r[i] == INF) break;
    pre[i] = pre[i - 1] + (r[i] - i);
  }
  int m = 0;
  for (int i = 1; i <= n; i++) {
    if (r[i] <= i + 1)
      cout << "error: "
           << "i = " << i << " r[i] = " << r[i] << endl;
    if (r[i] < m)
      cout << "error: "
           << "i = " << i << " r[i] = " << r[i] << " m = " << m << endl;
    m = max(m, r[i]);
  }
  ans1.clear();
  for (int i = 0; i < q; i++) {
    int L = qa[i], R = qb[i], a = qa[i], b = qb[i];
    while (L < R) {
      int M = L + (R - L) / 2;
      if (r[M] <= b)
        L = M + 1;
      else
        R = M;
    }
    long long t = b - L + 1;
    long long ans = t * (t + 1) / 2 + pre[L - 1] - pre[a - 1];
    ans1.push_back(ans);
  }
}
void solve2() {
  d[0] = -1;
  num = dfs_clock = 0;
  memset(vis, 0, sizeof(vis));
  for (int i = 0; i <= n; i++) r[i] = INF;
  for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
      dfs(i, 0);
    }
  }
  while (!S.empty()) S.pop();
  for (int i = 1; i <= n; i++) {
    if (r[i] != INF) {
      if (!S.empty() && r[i] <= S.top().second) S.pop();
      S.push(make_pair(i, r[i]));
    }
  }
  int b = INF, p = n;
  while (!S.empty()) {
    int x = S.top().first, y = S.top().second;
    S.pop();
    while (p > x) {
      r[p--] = b;
    }
    b = y;
  }
  while (p >= 1) r[p--] = b;
  ans2.clear();
  for (int i = 0; i < q; i++) {
    int a = qa[i], b = qb[i];
    long long ans = 0;
    for (int j = a; j <= b; j++) {
      ans += min(b + 1, r[j]) - j;
    }
    ans2.push_back(ans);
  }
}
int main() {
  while (cin >> n >> m) {
    for (int i = 0; i <= n; i++) G[i].clear();
    for (int i = 0; i < m; i++) {
      int u, v;
      scanf("%d%d", &u, &v);
      G[u].push_back(v);
      G[v].push_back(u);
    }
    cin >> q;
    for (int i = 0; i < q; i++) scanf("%d%d", &qa[i], &qb[i]);
    solve1();
    for (int i = 0; i < q; i++) printf("%lld\n", ans1[i]);
  }
  return 0;
}

```