← 返回题目列表

Codeforces · 901/C

C. 二分段

中文机器翻译题面 查看原题

给你一个有 n 个顶点的无向图。不存在长度相等的单边循环。换句话说,不存在最多通过每条边一次的长度相等的循环。让我们枚举从 1 到 n 的顶点。

您必须回答 q 个询问。每个查询由一段顶点 [l; r],并且你必须计算它的子段的数量 [x; y] (l ≤ x ≤ y ≤ r),这样如果我们删除除顶点段 [x; 之外的所有顶点; y](包括 x 和 y)以及它们之间的边,所得图是二分图。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 3·105, 1 ≤ m ≤ 3·105) - 图中的顶点数和边数。

接下来的 m 行描述图中的边。这些行的第 i 行包含两个整数 ai 和 bi (1 ≤ ai, bi ≤ n; ai ≠ bi),表示顶点 ai 和 bi 之间的边。保证该图不包含偶数长度的简单边循环。

下一行包含一个整数 q (1 ≤ q ≤ 3·105) — 查询数。

接下来的 q 行包含查询。这些行的第 i 行包含两个整数 li 和 ri (1 ≤ li ≤ ri ≤ n) — 查询参数。

输出

打印 q 个数字,每个数字换行:其中第 i 个数字应该是子段的数量 [x; y] (li ≤ x ≤ y ≤ ri),使得图仅包含线段 [x; 中的顶点; y] 并且它们之间的边是二分的。

示例

输入 #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

注意

第一个示例如下图所示:

对于第一个查询,[1; 的所有子段3],除了这个部分本身,都是合适的。

对于第一个查询,[4; 的所有子段6],除了这一段本身,都是合适的。

对于第三个查询,[1; 的所有子段6] 都是合适的,除了 [1; 3],[1; 4],[1; 5],[1; 6],[2; 6],[3; 6],[4; 6]。

第二个例子如下图所示: