Perhaps today and/or tomorrow due to a power outage there may be disruptions in the work of Codeforces and Polygon. Please do not plan any important events during this time. If there are details or the exact time, we will definitely publish them. Estimated time of maintenance: from 2 Aug, 16:00 (UTC) to 2 Aug, 20:00 (UTC).
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

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-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/02/2021 20:01:20 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|