Bipartite Segments
Contest: Codeforces Round 453 (Div. 1)
Difficulty rating: 2300
Tags: binary search, data structures, dfs and similar, dsu, graphs, two pointers

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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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:

Example input:
6 6
1 2
2 3
3 1
4 5
5 6
6 4
3
1 3
4 6
1 6

Example output:
5
5
14

Example 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

Example output:
27
8
19

Editorial:
If two cycles of odd length intersect, then they can be bypassed so as to obtain an edge-simple cycle of even length.
It follows that the given graph is a vertex cactus, with cycles of odd length, then the vertex segment is good - if there is no loop, that the vertex with the minimum number from this cycle is present on this segment and the vertex with the maximum number from this cycle is present on this segment. Then we can select all the cycles, and now we work with the segments.
Let us find for each vertex a maximal right boundary such that the interval [i..mxi] is a bipartite graph.
Then mxi is equal to the minimal right boundary of the segment, which was opened later i.
This can be considered a minimum on the suffix, initially setting for all cycles mx[minimum on the cycle] = maximum on the cycle
To answer the query, we need to take the sum over mxi - i + 1 for those who have mxi ≥ r and the sum over r - i + 1 for those who have mxi ≥ r
then we note that mxi increases and we simply need to find the first moment when mxi becomes  ≥ r (we can do it with binary search)
And take two prefix sums - sum of (mxi - i + 1) and sum of i.