| Codeforces Round 453 (Div. 1) |
|---|
| Закончено |
Дан неориентированный граф на 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] и ребра между этими вершинами, является двудольным.
6 6
1 2
2 3
3 1
4 5
5 6
6 4
3
1 3
4 6
1 6
5
5
14
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
27
8
19
Первый пример расположен на следующей картинке:
На первый запрос подходят все подотрезки отрезка [1; 3], кроме него самого.
На второй запрос подходят все подотрезки отрезка [4; 6], кроме него самого.
На третий запрос подходят все подотрезки отрезка [1; 6], кроме [1; 3], [1; 4], [1; 5], [1; 6], [2; 6], [3; 6], [4; 6].
Второй пример расположен на следующей картинке:
