C. Bipartite Segmentstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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.InputThe 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.OutputPrint 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.ExamplesInput6 61 22 33 14 55 66 431 34 61 6Output5514Input8 91 22 33 14 55 66 77 88 47 231 81 43 8Output27819NoteThe 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:
Input6 61 22 33 14 55 66 431 34 61 6
Output5514
['binary search', 'data structures', 'dfs and similar', 'dsu', 'graphs', 'two pointers', '*2300']