#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3 * (1e5) + 5;
int n, m, Q;
int u, v;
vector<int> graph[MAXN];
int cyclesCount = 0;
int node2Cycle[MAXN];
vector<int> cycle[MAXN];
int parent[MAXN];
set<pair<int, int> > used;
bool usedNodes[MAXN];
int maxLeft[MAXN];
long long dp[MAXN];
long long prefix[MAXN];
void DFS(int x) {
  usedNodes[x] = true;
  for (int i = 0; i < graph[x].size(); i++) {
    u = x;
    v = graph[x][i];
    if (used.count(make_pair(min(u, v), max(u, v))) == false) {
      used.insert(make_pair(min(u, v), max(u, v)));
      if (usedNodes[v] == false) {
        parent[v] = u;
        DFS(v);
      } else {
        while (u != v) {
          node2Cycle[u] = cyclesCount;
          cycle[cyclesCount].push_back(u);
          u = parent[u];
        }
        node2Cycle[v] = cyclesCount;
        cycle[cyclesCount].push_back(v);
        cyclesCount++;
      }
    }
  }
}
long long sum(long long x) {
  if (x % 2 != 0) {
    return sum(x - 1) + x;
  }
  return (x + 1) * (x / 2);
}
long long getSum(int l, int r) { return sum(r) - sum(l - 1); }
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  long long L, R;
  long long l, r, mid;
  long long answer = 0;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> u >> v;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) {
    DFS(i);
  }
  for (int i = 0; i < cyclesCount; i++) {
    sort(cycle[i].begin(), cycle[i].end());
  }
  dp[1] = 1;
  for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + i;
  L = 1;
  R = 1;
  maxLeft[1] = 1;
  for (R = 2; R <= n; R++) {
    if (cyclesCount != 0) {
      while (cycle[node2Cycle[R]][0] >= L &&
             cycle[node2Cycle[R]][cycle[node2Cycle[R]].size() - 1] <= R) {
        L++;
      }
    }
    maxLeft[R] = L;
  }
  prefix[1] = 1;
  for (int i = 2; i <= n; i++) prefix[i] = prefix[i - 1] + i - maxLeft[i] + 1;
  cin >> Q;
  for (int q = 0; q < Q; q++) {
    cin >> L >> R;
    answer = 0;
    l = L;
    r = R;
    while (l + 1 < r) {
      mid = (l + r) / 2;
      if (maxLeft[mid] <= L)
        l = mid;
      else
        r = mid - 1;
    }
    if (maxLeft[r] <= L) {
      answer = getSum(L, r) - L * (r - L + 1) + (r - L + 1);
      answer += prefix[R] - prefix[r];
    } else if (maxLeft[l] <= L) {
      answer = getSum(L, l) - L * (l - L + 1) + (l - L + 1);
      answer += prefix[R] - prefix[l];
    }
    cout << answer << '\n';
  }
}

### Prompt

Please create a solution in CPP 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;
const int MAXN = 3 * (1e5) + 5;
int n, m, Q;
int u, v;
vector<int> graph[MAXN];
int cyclesCount = 0;
int node2Cycle[MAXN];
vector<int> cycle[MAXN];
int parent[MAXN];
set<pair<int, int> > used;
bool usedNodes[MAXN];
int maxLeft[MAXN];
long long dp[MAXN];
long long prefix[MAXN];
void DFS(int x) {
  usedNodes[x] = true;
  for (int i = 0; i < graph[x].size(); i++) {
    u = x;
    v = graph[x][i];
    if (used.count(make_pair(min(u, v), max(u, v))) == false) {
      used.insert(make_pair(min(u, v), max(u, v)));
      if (usedNodes[v] == false) {
        parent[v] = u;
        DFS(v);
      } else {
        while (u != v) {
          node2Cycle[u] = cyclesCount;
          cycle[cyclesCount].push_back(u);
          u = parent[u];
        }
        node2Cycle[v] = cyclesCount;
        cycle[cyclesCount].push_back(v);
        cyclesCount++;
      }
    }
  }
}
long long sum(long long x) {
  if (x % 2 != 0) {
    return sum(x - 1) + x;
  }
  return (x + 1) * (x / 2);
}
long long getSum(int l, int r) { return sum(r) - sum(l - 1); }
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  long long L, R;
  long long l, r, mid;
  long long answer = 0;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> u >> v;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) {
    DFS(i);
  }
  for (int i = 0; i < cyclesCount; i++) {
    sort(cycle[i].begin(), cycle[i].end());
  }
  dp[1] = 1;
  for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + i;
  L = 1;
  R = 1;
  maxLeft[1] = 1;
  for (R = 2; R <= n; R++) {
    if (cyclesCount != 0) {
      while (cycle[node2Cycle[R]][0] >= L &&
             cycle[node2Cycle[R]][cycle[node2Cycle[R]].size() - 1] <= R) {
        L++;
      }
    }
    maxLeft[R] = L;
  }
  prefix[1] = 1;
  for (int i = 2; i <= n; i++) prefix[i] = prefix[i - 1] + i - maxLeft[i] + 1;
  cin >> Q;
  for (int q = 0; q < Q; q++) {
    cin >> L >> R;
    answer = 0;
    l = L;
    r = R;
    while (l + 1 < r) {
      mid = (l + r) / 2;
      if (maxLeft[mid] <= L)
        l = mid;
      else
        r = mid - 1;
    }
    if (maxLeft[r] <= L) {
      answer = getSum(L, r) - L * (r - L + 1) + (r - L + 1);
      answer += prefix[R] - prefix[r];
    } else if (maxLeft[l] <= L) {
      answer = getSum(L, l) - L * (l - L + 1) + (l - L + 1);
      answer += prefix[R] - prefix[l];
    }
    cout << answer << '\n';
  }
}

```