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>
#include <bits/stdc++.h>
using namespace std;
const int block = 512;
const int N = 3e5 + 5;
long long cur_ans, ans[N];
int n, m, h[N], up[N], rright[N], lleft[N], col[N], t[4 * N], cur_l, cur_r, c,
    mn[N], mx[N], q, cnt[N];
vector<pair<pair<int, int>, int> > query;
vector<pair<int, int> > g[N], edges;
bool was[N], bridge[N];
void dfs_h(int x, int hh) {
  was[x] = true;
  h[x] = hh;
  for (auto pr : g[x]) {
    int to = pr.first;
    if (!was[to]) dfs_h(to, hh + 1);
  }
}
void dfs_up(int x, int p) {
  was[x] = true;
  up[x] = h[x];
  for (auto pr : g[x]) {
    int to = pr.first;
    int edge = pr.second;
    if (to == p) continue;
    if (was[to]) {
      up[x] = min(up[x], h[to]);
      continue;
    }
    dfs_up(to, x);
    up[x] = min(up[x], up[to]);
    if (up[to] > h[x]) bridge[edge] = true;
  }
}
void dfs_cycles(int x) {
  was[x] = true;
  col[x] = c;
  for (auto pr : g[x]) {
    int to = pr.first;
    int edge = pr.second;
    if (bridge[edge]) continue;
    if (was[to]) continue;
    dfs_cycles(to);
  }
}
void update_min(int v, int pos, int tl, int tr, int value) {
  if (pos < tl || pos > tr) return;
  if (pos == tl && pos == tr) {
    t[v] = value;
    return;
  }
  int tm = (tl + tr) / 2;
  update_min(2 * v + 1, pos, tl, tm, value);
  update_min(2 * v + 2, pos, tm + 1, tr, value);
  t[v] = min(t[2 * v + 1], t[2 * v + 2]);
}
int get_min(int v, int l, int r, int tl, int tr) {
  if (r < l) return n - 1;
  if (l == tl && r == tr) {
    return t[v];
  }
  int tm = (tl + tr) / 2;
  int lValue = get_min(2 * v + 1, l, min(r, tm), tl, tm);
  int rValue = get_min(2 * v + 2, max(l, tm + 1), r, tm + 1, tr);
  return min(lValue, rValue);
}
void update_max(int v, int pos, int tl, int tr, int value) {
  if (pos < tl || pos > tr) return;
  if (pos == tl && pos == tr) {
    t[v] = value;
    return;
  }
  int tm = (tl + tr) / 2;
  update_max(2 * v + 1, pos, tl, tm, value);
  update_max(2 * v + 2, pos, tm + 1, tr, value);
  t[v] = max(t[2 * v + 1], t[2 * v + 2]);
}
int get_max(int v, int l, int r, int tl, int tr) {
  if (r < l) return 0;
  if (l == tl && r == tr) return t[v];
  int tm = (tl + tr) / 2;
  int lValue = get_max(2 * v + 1, l, min(r, tm), tl, tm);
  int rValue = get_max(2 * v + 2, max(l, tm + 1), r, tm + 1, tr);
  return max(lValue, rValue);
}
bool comp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
  auto aa = a.first;
  auto bb = b.first;
  if (aa == bb) return a.second < b.second;
  if (aa.first / block != bb.first / block)
    return aa.first / block < bb.first / block;
  return aa.second < bb.second;
}
void solve(int l, int r) {
  while (cur_l != l || cur_r != r) {
    while (cur_l != l) {
      if (cur_l == cur_r && l > cur_l) break;
      if (cur_l < l) {
        if (rright[cur_l] <= cur_r)
          cur_ans -= (rright[cur_l] - cur_l + 1);
        else
          cur_ans -= (cur_r - cur_l + 1);
        cur_l++;
      } else {
        cur_l--;
        if (rright[cur_l] <= cur_r)
          cur_ans += (rright[cur_l] - cur_l + 1);
        else
          cur_ans += (cur_r - cur_l + 1);
      }
    }
    while (cur_r != r) {
      if (cur_l == cur_r && r < cur_r) break;
      if (cur_r < r) {
        cur_r++;
        if (lleft[cur_r] >= cur_l)
          cur_ans += (cur_r - lleft[cur_r] + 1);
        else
          cur_ans += (cur_r - cur_l + 1);
      } else {
        if (lleft[cur_r] >= cur_l)
          cur_ans -= (cur_r - lleft[cur_r] + 1);
        else
          cur_ans -= (cur_r - cur_l + 1);
        cur_r--;
      }
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    g[a].push_back({b, i});
    g[b].push_back({a, i});
    edges.push_back({a, b});
  }
  for (int i = 0; i < n; i++)
    if (!was[i]) dfs_h(i, 0);
  for (int i = 0; i < n; i++) was[i] = false;
  for (int i = 0; i < n; i++)
    if (!was[i]) dfs_up(i, -1);
  for (int i = 0; i < n; i++) was[i] = false;
  for (int i = 0; i < n; i++)
    if (!was[i]) {
      dfs_cycles(i);
      c++;
    }
  for (int i = 0; i < n; i++) mn[i] = n - 1;
  for (int i = 0; i < n; i++) {
    int c = col[i];
    cnt[c]++;
    mx[c] = max(mx[c], i);
    mn[c] = min(mn[c], i);
  }
  for (int i = 0; i < n; i++) {
    int c = col[i];
    if (cnt[c] == 1) {
      lleft[i] = 0;
      rright[i] = n - 1;
      continue;
    }
    if (i != mn[c])
      rright[i] = n - 1;
    else
      rright[i] = mx[c] - 1;
    if (i != mx[c])
      lleft[i] = 0;
    else
      lleft[i] = mn[c] + 1;
  }
  for (int i = 0; i < n; i++) update_min(0, i, 0, n - 1, rright[i]);
  for (int i = n - 2; i >= 0; i--) {
    int value = get_min(0, i, rright[i], 0, n - 1);
    update_min(0, i, 0, n - 1, value);
  }
  for (int i = 0; i < n; i++) rright[i] = get_min(0, i, i, 0, n - 1);
  for (int i = 0; i < n; i++) update_max(0, i, 0, n - 1, lleft[i]);
  for (int i = 1; i < n; i++) {
    int value = get_max(0, lleft[i], i, 0, n - 1);
    update_max(0, i, 0, n - 1, value);
  }
  for (int i = 0; i < n; i++) lleft[i] = get_max(0, i, i, 0, n - 1);
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    l--;
    r--;
    query.push_back({{l, r}, i});
  }
  sort(query.begin(), query.end(), comp);
  cur_ans = 1;
  for (int i = 0; i < query.size(); i++) {
    int l = query[i].first.first;
    int r = query[i].first.second;
    solve(l, r);
    ans[query[i].second] = cur_ans;
  }
  for (int i = 0; i < q; i++) cout << ans[i] << "\n";
  return 0;
}
