给你一个有 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]。
第二个例子如下图所示: