No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Bipartite Segments

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Input

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.

Output

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.

Examples

Input

6 6

1 2

2 3

3 1

4 5

5 6

6 4

3

1 3

4 6

1 6

Output

5

5

14

Input

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

Output

27

8

19

Note

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:

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/17/2022 11:27:53 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|