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.
The first line contains two integers *n* and *m* (1 ≤ *n* ≤ 3·10<sup class="upper-index">5</sup>, 1 ≤ *m* ≤ 3·10<sup class="upper-index">5</sup>) — 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 *a*<sub class="lower-index">*i*</sub> and *b*<sub class="lower-index">*i*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> ≤ *n*; *a*<sub class="lower-index">*i*</sub> ≠ *b*<sub class="lower-index">*i*</sub>), denoting an edge between vertices *a*<sub class="lower-index">*i*</sub> and *b*<sub class="lower-index">*i*</sub>. 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·10<sup class="upper-index">5</sup>) — the number of queries.

The next *q* lines contain queries. The *i*-th of these lines contains two integers *l*<sub class="lower-index">*i*</sub> and *r*<sub class="lower-index">*i*</sub> (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*) — the query parameters.
The first example is shown on the picture below:

<img class="tex-graphics" src="https://espresso.codeforces.com/01e1d1999228f416613ff64b5d0e0cf984f150b1.png" style="max-width: 100.0%;max-height: 100.0%;"/>

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:

<img class="tex-graphics" src="https://espresso.codeforces.com/09b9227070585b8d5a7dff3cbc5f8535c260a595.png" style="max-width: 100.0%;max-height: 100.0%;"/>
class Vertex:
    adj = []


n, m = input().split()
n = int(n)
m = int(m)
adj = []

for _ in range(0, n):
    adj.append([])
for x in range(0, m):
    a, b = input().split()
    a = int(a) - 1
    b = int(b) - 1
    adj[a].append(b)
    adj[b].append(a)

rightmost = []
for s in range(0, n):
    trees = [[s]]
    trees_union = set().union(*trees)
    for i in range(s + 1, n):
        test = 0
        allinone = []
        indices = []
        for j in range(0, len(trees)):
            if len(set(adj[i]) & set(trees[j])) >= 2:
                test = 1
                break
            elif len(set(adj[i]) & set(trees[j])) == 1:
                allinone.append(trees[j])
                indices.append(j)
        if test:
            rightmost.append(i - 1)
            break
        result = list(set().union(*allinone))
        result.append(i)
        trees.pop(*indices)
        trees.append(result)
        if i == n - 1:
            rightmost.append(i)
rightmost.append(n-1)
assert len(rightmost) == n

queries = int(input())
answer = []
for _ in range(0, queries):
    x, y= input().split()
    x = int(x) - 1
    y = int(y) - 1
    sum = 0
    for t in range(x, y+1):
        sum += min(y, rightmost[t]) - t + 1
    answer.append(sum)
for i in answer:
    print(i)