Дан неориентированный граф на n вершинах, в котором нет реберно-простых циклов четной длины (циклов четной длины, которые не проходят по одному ребру два раза). Будем считать, что вершины графа пронумерованы целыми числами от 1 до n.
Требуется ответить на q запросов. Каждый запрос задается отрезком вершин [l; r], требуется посчитать количество его подотрезков [x; y] (l ≤ x ≤ y ≤ r) таких, что граф, в котором оставили только вершины из отрезка [x; y] (включая и x, и y) и ребра между этими вершинами, является двудольным.
Выходные данные
Выведите q чисел, каждое в новой строке: i-е из них равно количеству таких подотрезков [x; y] (li ≤ x ≤ y ≤ ri), что граф, в котором оставили только вершины из отрезка [x; y] и ребра между этими вершинами, является двудольным.
Примечание
Первый пример расположен на следующей картинке:
На первый запрос подходят все подотрезки отрезка [1; 3], кроме него самого.
На второй запрос подходят все подотрезки отрезка [4; 6], кроме него самого.
На третий запрос подходят все подотрезки отрезка [1; 6], кроме [1; 3], [1; 4], [1; 5], [1; 6], [2; 6], [3; 6], [4; 6].
Второй пример расположен на следующей картинке:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 6
1 2
2 3
3 1
4 5
5 6
6 4
3
1 3
4 6
1 6
|
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
|
27
8
19
|