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 MAXN = 300005;
vector<int> adj[MAXN], bcc[MAXN], color[MAXN];
int low[MAXN], dfn[MAXN], n, step, vis[MAXN], col, test = 0, m;
int root[MAXN];
set<int> co;
int timer = 0;
void dfs(int here, int dad) {
  low[here] = dfn[here] = ++step;
  for (int i = 0; i < adj[here].size(); i++) {
    int there = adj[here][i];
    if (dad == there) continue;
    if (!dfn[there]) {
      dfs(there, here);
      low[here] = min(low[here], low[there]);
    } else
      low[here] = min(low[here], dfn[there]);
  }
}
void paint(int here, int c) {
  vis[here] = 1;
  if (c != 0) co.insert(c);
  if (c) bcc[here].push_back(c), color[c].push_back(here);
  for (int i = 0; i < adj[here].size(); i++) {
    int there = adj[here][i];
    if (vis[there]) continue;
    if (low[there] >= dfn[here]) {
      bcc[here].push_back(++col);
      color[col].push_back(here);
      paint(there, col);
    } else {
      paint(there, c);
    }
  }
}
struct segTree {
  vector<long long> tree, lazy, mn;
  void init(int n) {
    tree.resize(4 * n + 1, 0);
    lazy.resize(4 * n + 1, 0);
    mn.resize(4 * n + 1, 0);
  }
  void push(int node, int st, int ed) {
    tree[node] += (lazy[node] * (ed - st + 1));
    mn[node] += lazy[node];
    if (st != ed) {
      lazy[node * 2] += lazy[node];
      lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
  }
  void update(int node, int st, int ed, int l, int r, long long val) {
    push(node, st, ed);
    if (st > r || ed < l) return;
    if (st >= l && ed <= r) {
      lazy[node] += val;
      push(node, st, ed);
      return;
    }
    update(node * 2, st, (st + ed) / 2, l, r, val);
    update(node * 2 + 1, (st + ed) / 2 + 1, ed, l, r, val);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
    mn[node] = min(mn[node * 2], mn[node * 2 + 1]);
  }
  pair<long long, long long> query(int node, int st, int ed, int l, int r) {
    push(node, st, ed);
    if (st > r || ed < l) return {1e18, 0};
    if (st >= l && ed <= r) return {mn[node], tree[node]};
    auto L = query(node * 2, st, (st + ed) / 2, l, r);
    auto R = query(node * 2 + 1, (st + ed) / 2 + 1, ed, l, r);
    return make_pair(min(L.first, R.first), L.second + R.second);
  }
} segt;
int lt[MAXN];
vector<int> seg[MAXN];
vector<int> stt[MAXN];
void solve() {
  step = 0;
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) {
    if (dfn[i] == 0) {
      col = 0;
      dfs(i, -1);
      paint(i, 0);
      for (auto it : co) {
        int mn = 1e9;
        int mx = -1e9;
        for (int j = 0; j < color[it].size(); j++) {
          mn = min(mn, color[it][j]);
          mx = max(mx, color[it][j]);
        }
        if (color[it].size() > 2) seg[mx].push_back(mn);
        color[it].clear();
      }
    }
  }
  int j = 1;
  for (int i = 1; i <= n; i++) {
    for (auto it : seg[i]) {
      while (j < n && it >= j) j++;
    }
    lt[i] = j;
    stt[lt[i]].push_back(i);
  }
}
vector<pair<int, int> > vx;
vector<pair<int, int> > query[MAXN];
long long psum[MAXN];
long long ans[MAXN];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();
  int q;
  cin >> q;
  for (int i = 1; i <= n; i++) {
    psum[i] += (psum[i - 1] + (i - lt[i] + 1));
  }
  segt.init(n);
  for (int i = 1; i <= q; i++) {
    int l, r;
    cin >> l >> r;
    query[l].push_back({r, i});
  }
  for (int i = 1; i <= n; i++) {
    segt.update(1, 1, n, i, i, i - lt[i] + 1);
  }
  int mx = 1;
  for (int i = 1; i <= n; i++) {
    for (auto it : query[i]) {
      int l = i;
      int r = it.first;
      int id = it.second;
      ans[id] = segt.query(1, 1, n, l, r).second;
    }
    for (auto it : stt[i]) {
      mx = max(mx, it);
    }
    segt.update(1, 1, n, 1, mx, -1);
  }
  for (int i = 1; i <= q; i++) {
    cout << ans[i] << "\n";
  }
  return 0;
}
