A11370 | 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 line contains two integers $n$ and $m$ ( $1<=n<=3·10^{5}$ , $1<=m<=3·10^{5}$ ) — 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_{i}$ and $b_{i}$ ( $1<=a_{i},b_{i}<=n$ ; $a_{i}≠b_{i}$ ), denoting an edge between vertices $a_{i}$ and $b_{i}$ . 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^{5}$ ) — the number of queries.

The next $q$ lines contain queries. The $i$ -th of these lines contains two integers $l_{i}$ and $r_{i}$ ( $1<=l_{i}<=r_{i}<=n$ ) — the query parameters.

Print $q$ numbers, each in new line: the $i$ -th of them should be the number of subsegments $[x;y]$ ( $l_{i}<=x<=y<=r_{i}$ ), such that the graph that only includes vertices from segment $[x;y]$ and edges between them is bipartite.