Bipartite Segments
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 example is shown on the picture below: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:
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.
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.
from io import BytesIO, IOBase
import sys
import os
import bisect
import math
import random
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
from itertools import accumulate, combinations, permutations, count
from operator import add, iand, ior, itemgetter, mul, xor
from string import ascii_lowercase, ascii_uppercase
from typing import *

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
BUFSIZE = 5096

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
inf = float('inf')
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
(n, m) = MII()
path = [[] for _ in range(n)]
for _ in range(m):
    (u, v) = GMI()
    path[u].append(v)
    path[v].append(u)
dfn = [0] * n
low = [0] * n
col = [-1] * n
color = tmstamp = 0
stack = []

@bootstrap
def tarjan(u, f):
    global color, tmstamp
    tmstamp += 1
    dfn[u] = low[u] = tmstamp
    stack.append(u)
    for v in path[u]:
        if dfn[v] == 0:
            yield tarjan(v, u)
            low[u] = min(low[u], low[v])
        elif v != f:
            low[u] = min(low[u], dfn[v])
    if low[u] == dfn[u]:
        while True:
            col[stack[-1]] = color
            tmp = stack.pop()
            if tmp == u:
                break
        color += 1
    yield
for i in range(n):
    if col[i] == -1:
        tarjan(i, -1)
del dfn, low, path
lefts = [inf] * color
rights = [-inf] * color
for i in range(n):
    lefts[col[i]] = min(lefts[col[i]], i)
    rights[col[i]] = max(rights[col[i]], i)
right_max = [n] * n
for i in range(color):
    if lefts[i] != rights[i]:
        right_max[lefts[i]] = rights[i]
right_count = [1] * n
curr = n
for i in range(n - 2, -1, -1):
    curr = min(curr, right_max[i])
    right_count[i] = curr - i
    right_max[i] = curr
right_count_acc = [0] + list(accumulate(right_count))
q = II()
queries = [[] for _ in range(n)]
for i in range(q):
    (l, r) = GMI()
    queries[r].append((i, l))
ans = [None] * q
pt = 0
for r in range(n):
    while pt < n and right_max[pt] <= r:
        pt += 1
    for (idx, l) in queries[r]:
        if r < pt:
            ans[idx] = right_count_acc[pt] - right_count_acc[l]
        elif pt <= l:
            ans[idx] = (r - l + 1) * (r - l + 2) // 2
        else:
            ans[idx] = right_count_acc[pt] - right_count_acc[l] + (r - pt + 1) * (r - pt + 2) // 2
print(*ans, sep='\n')
def divisors(M):
    d = []
    i = 1
    while M >= i ** 2:
        if M % i == 0:
            d.append(i)
            if i ** 2 != M:
                d.append(M // i)
        i = i + 1
    return d

def popcount(x):
    x = x - (x >> 1 & 1431655765)
    x = (x & 858993459) + (x >> 2 & 858993459)
    x = x + (x >> 4) & 252645135
    x = x + (x >> 8)
    x = x + (x >> 16)
    return x & 127

def eratosthenes(n):
    res = [0 for i in range(n + 1)]
    prime = set([])
    for i in range(2, n + 1):
        if not res[i]:
            prime.add(i)
            for j in range(1, n // i + 1):
                res[i * j] = 1
    return prime

def factorization(n):
    res = []
    for p in prime:
        if n % p == 0:
            while n % p == 0:
                n //= p
            res.append(p)
    if n != 1:
        res.append(n)
    return res

def euler_phi(n):
    res = n
    for x in range(2, n + 1):
        if x ** 2 > n:
            break
        if n % x == 0:
            res = res // x * (x - 1)
            while n % x == 0:
                n //= x
    if n != 1:
        res = res // n * (n - 1)
    return res

def ind(b, n):
    res = 0
    while n % b == 0:
        res += 1
        n //= b
    return res

def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 3, 5, 7, 11, 13, 17]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1:
            continue
        while y != n - 1:
            y = y * y % n
            if y == 1 or t == n - 1:
                return 0
            t <<= 1
    return 1

def findFactorRho(n):
    from math import gcd
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        (y, r, q, g) = (2, 1, 1, 1)
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g):
                return g
            elif isPrimeMR(n // g):
                return n // g
            return findFactorRho(g)

def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k:
            ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    (ret[n], n) = (1, 1)
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k
    if n > 1:
        ret[n] = 1
    if rhoFlg:
        ret = {x: ret[x] for x in sorted(ret)}
    return ret

def divisors(n):
    res = [1]
    prime = primeFactor(n)
    for p in prime:
        newres = []
        for d in res:
            for j in range(prime[p] + 1):
                newres.append(d * p ** j)
        res = newres
    res.sort()
    return res

def xorfactorial(num):
    if num == 0:
        return 0
    elif num == 1:
        return 1
    elif num == 2:
        return 3
    elif num == 3:
        return 0
    else:
        x = baseorder(num)
        return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
    if n == 0:
        res = [X[0] * Y[0] % mod]
        return res
    x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
    y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
    z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
    w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
    res1 = xorconv(n - 1, x, y)
    res2 = xorconv(n - 1, z, w)
    former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
    latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
    former = list(map(lambda x: x % mod, former))
    latter = list(map(lambda x: x % mod, latter))
    return former + latter

def merge_sort(A, B):
    (pos_A, pos_B) = (0, 0)
    (n, m) = (len(A), len(B))
    res = []
    while pos_A < n and pos_B < m:
        (a, b) = (A[pos_A], B[pos_B])
        if a < b:
            res.append(a)
            pos_A += 1
        else:
            res.append(b)
            pos_B += 1
    res += A[pos_A:]
    res += B[pos_B:]
    return res

class UnionFindVerSize:

    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N
        self.group = N

    def find_root(self, x):
        if self._parent[x] == x:
            return x
        self._parent[x] = self.find_root(self._parent[x])
        stack = [x]
        while self._parent[stack[-1]] != stack[-1]:
            stack.append(self._parent[stack[-1]])
        for v in stack:
            self._parent[v] = stack[-1]
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy:
            return
        self.group -= 1
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for i in range(N)]
        self.val = [0 for i in range(N)]
        self.flag = True
        self.edge = [[] for i in range(N)]

    def dfs(self, v, pv):
        stack = [(v, pv)]
        new_parent = self.parent[pv]
        while stack:
            (v, pv) = stack.pop()
            self.parent[v] = new_parent
            for (nv, w) in self.edge[v]:
                if nv != pv:
                    self.val[nv] = self.val[v] + w
                    stack.append((nv, v))

    def unite(self, x, y, w):
        if not self.flag:
            return
        if self.parent[x] == self.parent[y]:
            self.flag = self.val[x] - self.val[y] == w
            return
        if self.size[self.parent[x]] > self.size[self.parent[y]]:
            self.edge[x].append((y, -w))
            self.edge[y].append((x, w))
            self.size[x] += self.size[y]
            self.val[y] = self.val[x] - w
            self.dfs(y, x)
        else:
            self.edge[x].append((y, -w))
            self.edge[y].append((x, w))
            self.size[y] += self.size[x]
            self.val[x] = self.val[y] + w
            self.dfs(x, y)

class Dijkstra:

    class Edge:

        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        self.G = [[] for i in range(V)]
        self._E = 0
        self._V = V

    @property
    def E(self):
        return self._E

    @property
    def V(self):
        return self._V

    def add_edge(self, _from, _to, _cost):
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        import heapq
        que = []
        d = [10 ** 15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))
        while len(que) != 0:
            (cost, v) = heapq.heappop(que)
            if d[v] < cost:
                continue
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost
                    heapq.heappush(que, (d[e.to], e.to))
        return d

def Z_algorithm(s):
    N = len(s)
    Z_alg = [0] * N
    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i + j < N and s[j] == s[i + j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < N and k + Z_alg[k] < j:
            Z_alg[i + k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

class BIT:

    def __init__(self, n, mod=0):
        self.BIT = [0] * (n + 1)
        self.num = n
        self.mod = mod

    def query(self, idx):
        res_sum = 0
        mod = self.mod
        while idx > 0:
            res_sum += self.BIT[idx]
            if mod:
                res_sum %= mod
            idx -= idx & -idx
        return res_sum

    def update(self, idx, x):
        mod = self.mod
        while idx <= self.num:
            self.BIT[idx] += x
            if mod:
                self.BIT[idx] %= mod
            idx += idx & -idx
        return

class dancinglink:

    def __init__(self, n, debug=False):
        self.n = n
        self.debug = debug
        self._left = [i - 1 for i in range(n)]
        self._right = [i + 1 for i in range(n)]
        self.exist = [True for i in range(n)]

    def pop(self, k):
        if self.debug:
            assert self.exist[k]
        L = self._left[k]
        R = self._right[k]
        if L != -1:
            if R != self.n:
                (self._right[L], self._left[R]) = (R, L)
            else:
                self._right[L] = self.n
        elif R != self.n:
            self._left[R] = -1
        self.exist[k] = False

    def left(self, idx, k=1):
        if self.debug:
            assert self.exist[idx]
        res = idx
        while k:
            res = self._left[res]
            if res == -1:
                break
            k -= 1
        return res

    def right(self, idx, k=1):
        if self.debug:
            assert self.exist[idx]
        res = idx
        while k:
            res = self._right[res]
            if res == self.n:
                break
            k -= 1
        return res

class SparseTable:

    def __init__(self, A, merge_func, ide_ele):
        N = len(A)
        n = N.bit_length()
        self.table = [[ide_ele for i in range(n)] for i in range(N)]
        self.merge_func = merge_func
        for i in range(N):
            self.table[i][0] = A[i]
        for j in range(1, n):
            for i in range(0, N - 2 ** j + 1):
                f = self.table[i][j - 1]
                s = self.table[i + 2 ** (j - 1)][j - 1]
                self.table[i][j] = self.merge_func(f, s)

    def query(self, s, t):
        b = t - s + 1
        m = b.bit_length() - 1
        return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

    class node:

        def __init__(self, val):
            self.left = None
            self.right = None
            self.max = val

    def __init__(self):
        self.root = self.node(-10 ** 15)

    def append(self, key, val):
        pos = self.root
        for i in range(29, -1, -1):
            pos.max = max(pos.max, val)
            if key >> i & 1:
                if pos.right is None:
                    pos.right = self.node(val)
                    pos = pos.right
                else:
                    pos = pos.right
            elif pos.left is None:
                pos.left = self.node(val)
                pos = pos.left
            else:
                pos = pos.left
        pos.max = max(pos.max, val)

    def search(self, M, xor):
        res = -10 ** 15
        pos = self.root
        for i in range(29, -1, -1):
            if pos is None:
                break
            if M >> i & 1:
                if xor >> i & 1:
                    if pos.right:
                        res = max(res, pos.right.max)
                    pos = pos.left
                else:
                    if pos.left:
                        res = max(res, pos.left.max)
                    pos = pos.right
            elif xor >> i & 1:
                pos = pos.right
            else:
                pos = pos.left
        if pos:
            res = max(res, pos.max)
        return res

def solveequation(edge, ans, n, m):
    x = [0] * m
    used = [False] * n
    for v in range(n):
        if used[v]:
            continue
        y = dfs(v)
        if y != 0:
            return False
    return x

    def dfs(v):
        used[v] = True
        r = ans[v]
        for (to, dire, id) in edge[v]:
            if used[to]:
                continue
            y = dfs(to)
            if dire == -1:
                x[id] = y
            else:
                x[id] = -y
            r += y
        return r

class SegmentTree:

    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        self.size = n
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        if r == self.size:
            r = self.num
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

    def bisect_l(self, l, r, x):
        l += self.num
        r += self.num
        Lmin = -1
        Rmin = -1
        while l < r:
            if l & 1:
                if self.tree[l] <= x and Lmin == -1:
                    Lmin = l
                l += 1
            if r & 1:
                if self.tree[r - 1] <= x:
                    Rmin = r - 1
            l >>= 1
            r >>= 1
        if Lmin != -1:
            pos = Lmin
            while pos < self.num:
                if self.tree[2 * pos] <= x:
                    pos = 2 * pos
                else:
                    pos = 2 * pos + 1
            return pos - self.num
        elif Rmin != -1:
            pos = Rmin
            while pos < self.num:
                if self.tree[2 * pos] <= x:
                    pos = 2 * pos
                else:
                    pos = 2 * pos + 1
            return pos - self.num
        else:
            return -1
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
mi = lambda : map(int, input().split())
li = lambda : list(mi())
(n, m) = mi()
edge = [[] for i in range(n)]
for _ in range(m):
    (u, v) = mi()
    edge[u - 1].append(v - 1)
    edge[v - 1].append(u - 1)
parent = [-1 for i in range(n)]
depth = [0 for i in range(n)]
cnt = [0 for i in range(n)]
res = [n for i in range(n)]
for root in range(n):
    if parent[root] == -1:
        stack = [root]
        while stack:
            v = stack[-1]
            if len(edge[v]) == cnt[v]:
                stack.pop()
            else:
                nv = edge[v][cnt[v]]
                cnt[v] += 1
                if nv == root or parent[nv] != -1:
                    if depth[nv] < depth[v] - 1:
                        (m, M) = (nv, nv)
                        pos = v
                        while pos != nv:
                            m = min(pos, m)
                            M = max(pos, M)
                            pos = parent[pos]
                        res[m] = min(res[m], M)
                else:
                    depth[nv] = depth[v] + 1
                    parent[nv] = v
                    stack.append(nv)
cnt = [0 for i in range(n)]
cnt[n - 1] = res[n - 1] - (n - 1)
for i in range(n - 2, -1, -1):
    res[i] = min(res[i], res[i + 1])
    cnt[i] = res[i] - i
for i in range(1, n):
    cnt[i] += cnt[i - 1]
query = [[] for i in range(n + 1)]
q = int(input())
for i in range(q):
    (l, r) = mi()
    query[r].append((i, l - 1))
pos = -1
ans = [0 for i in range(q)]
for r in range(1, n + 1):
    while pos + 1 < n and res[pos + 1] <= r:
        pos += 1
    for (idx, l) in query[r]:
        if r <= pos:
            tmp = cnt[r - 1]
            if l:
                tmp -= cnt[l - 1]
        elif l <= pos:
            tmp = cnt[pos]
            if l:
                tmp -= cnt[l - 1]
            tmp += (r - pos - 1) * r - (r + pos) * (r - pos - 1) // 2
        else:
            tmp = (r - l) * r - (r - 1 + l) * (r - l) // 2
        ans[idx] = tmp
print(*ans, sep='\n')
from io import BytesIO, IOBase
import sys
import os
import bisect
import math
import random
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
from itertools import accumulate, combinations, permutations, count
from operator import add, iand, ior, itemgetter, mul, xor
from string import ascii_lowercase, ascii_uppercase
from typing import *

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
BUFSIZE = 5096

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
inf = float('inf')
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
(n, m) = MII()
path = [[] for _ in range(n)]
for _ in range(m):
    (u, v) = GMI()
    path[u].append(v)
    path[v].append(u)
dfn = [0] * n
low = [0] * n
col = [-1] * n
color = tmstamp = 0
stack = []

@bootstrap
def tarjan(u, f):
    global color, tmstamp
    tmstamp += 1
    dfn[u] = low[u] = tmstamp
    stack.append(u)
    for v in path[u]:
        if dfn[v] == 0:
            yield tarjan(v, u)
            low[u] = min(low[u], low[v])
        elif v != f:
            low[u] = min(low[u], dfn[v])
    if low[u] == dfn[u]:
        while True:
            col[stack[-1]] = color
            tmp = stack.pop()
            if tmp == u:
                break
        color += 1
    yield
for i in range(n):
    if col[i] == -1:
        tarjan(i, -1)
del dfn, low, path
lefts = [inf] * color
rights = [-inf] * color
for i in range(n):
    lefts[col[i]] = min(lefts[col[i]], i)
    rights[col[i]] = max(rights[col[i]], i)
right_max = [n] * n
for i in range(color):
    if lefts[i] != rights[i]:
        right_max[lefts[i]] = rights[i]
right_count = [1] * n
curr = n
for i in range(n - 2, -1, -1):
    curr = min(curr, right_max[i])
    right_count[i] = curr - i
    right_max[i] = curr
right_count_acc = [0] + list(accumulate(right_count))
q = II()
queries = [[] for _ in range(n)]
for i in range(q):
    (l, r) = GMI()
    queries[r].append((i, l))
ans = [None] * q
pt = 0
for r in range(n):
    while pt < n and right_max[pt] <= r:
        pt += 1
    for (idx, l) in queries[r]:
        if r < pt:
            ans[idx] = right_count_acc[pt] - right_count_acc[l]
        elif pt <= l:
            ans[idx] = (r - l + 1) * (r - l + 2) // 2
        else:
            ans[idx] = right_count_acc[pt] - right_count_acc[l] + (r - pt + 1) * (r - pt + 2) // 2
print(*ans, sep='\n')