Bipartite Segments

题意翻译

给你一个有$n$个点的无向图，没有偶环。我们把节点标记为$1..n$。 你需要回答$q$个询问，每一个询问由一个区间`[L,R](1<=L<=R<=n)`组成，你需要计算出有多少个点对`[x,y](L<=x<=y<=R)`，满足由`[x,y]`之间的所有点组成的子图是一个二分图。 输入数据第一行两个整数 $n,m$ ($1\le n\le 3\times 10^5,1\le m\le 3\times10^5$)代表点数和边数 接下来的$m$行，每行两个整数，表示一条无向边，保证无自环，保证无重边 一个整数 $q(1\le q\le3\times 10^5)$，表示询问个数 接下来$q$行，每行一个询问`[L,R]` 对于每个询问，输出一个整数，表示满足条件的点对`[x,y]`的个数

题目描述

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.

输入输出样例

输入样例 #1

6 6
1 2
2 3
3 1
4 5
5 6
6 4
3
1 3
4 6
1 6

输出样例 #1

5
5
14

输入样例 #2

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

输出样例 #2

27
8
19

说明

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: