You 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·105, 1 ≤ _m_ ≤ 3·105) — 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·105) — 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.
[samples]
## 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:
给定一个无向图，包含 #cf_span[n] 个顶点。图中不存在边简单偶环，即不存在经过每条边至多一次的偶数长度环。将顶点编号为 #cf_span[1] 到 #cf_span[n]。
你需要回答 #cf_span[q] 个查询。每个查询由一个顶点区间 #cf_span[[l; r]] 描述，你需要计算其子区间 #cf_span[[x; y]]（满足 #cf_span[l ≤ x ≤ y ≤ r]）的个数，使得当仅保留区间 #cf_span[[x; y]] 中的顶点（包括 #cf_span[x] 和 #cf_span[y]）以及它们之间的边时，所得子图是二分图。
第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 3·105]，#cf_span[1 ≤ m ≤ 3·105]），分别表示图的顶点数和边数。
接下来的 #cf_span[m] 行描述图中的边。第 #cf_span[i] 行包含两个整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1 ≤ ai, bi ≤ n]；#cf_span[ai ≠ bi]），表示顶点 #cf_span[ai] 和 #cf_span[bi] 之间有一条边。保证该图不含边简单偶环。
接下来一行包含一个整数 #cf_span[q]（#cf_span[1 ≤ q ≤ 3·105]），表示查询数量。
接下来的 #cf_span[q] 行包含查询。第 #cf_span[i] 行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li ≤ ri ≤ n]），表示查询参数。
请输出 #cf_span[q] 个数，每个数占一行：第 #cf_span[i] 个数应为满足条件的子区间 #cf_span[[x; y]]（#cf_span[li ≤ x ≤ y ≤ ri]）的数量，即仅包含区间 #cf_span[[x; y]] 中顶点及其之间边的子图是二分图。
第一个示例如下图所示：
对于第一个查询，区间 #cf_span[[1; 3]] 的所有子区间中，除了其自身以外都满足条件。
对于第一个查询，区间 #cf_span[[4; 6]] 的所有子区间中，除了其自身以外都满足条件。
对于第三个查询，区间 #cf_span[[1; 6]] 的所有子区间中，除了 #cf_span[[1; 3]]、#cf_span[[1; 4]]、#cf_span[[1; 5]]、#cf_span[[1; 6]]、#cf_span[[2; 6]]、#cf_span[[3; 6]]、#cf_span[[4; 6]] 之外都满足条件。
第二个示例如下图所示：
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 3·105]，#cf_span[1 ≤ m ≤ 3·105]），分别表示图的顶点数和边数。接下来的 #cf_span[m] 行描述图中的边。第 #cf_span[i] 行包含两个整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1 ≤ ai, bi ≤ n]；#cf_span[ai ≠ bi]），表示顶点 #cf_span[ai] 和 #cf_span[bi] 之间有一条边。保证该图不含边简单偶环。接下来一行包含一个整数 #cf_span[q]（#cf_span[1 ≤ q ≤ 3·105]），表示查询数量。接下来的 #cf_span[q] 行包含查询。第 #cf_span[i] 行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li ≤ ri ≤ n]），表示查询参数。
## Output
请输出 #cf_span[q] 个数，每个数占一行：第 #cf_span[i] 个数应为满足条件的子区间 #cf_span[[x; y]]（#cf_span[li ≤ x ≤ y ≤ ri]）的数量，即仅包含区间 #cf_span[[x; y]] 中顶点及其之间边的子图是二分图。
[samples]
## Note
第一个示例如下图所示：对于第一个查询，区间 #cf_span[[1; 3]] 的所有子区间中，除了其自身以外都满足条件。对于第一个查询，区间 #cf_span[[4; 6]] 的所有子区间中，除了其自身以外都满足条件。对于第三个查询，区间 #cf_span[[1; 6]] 的所有子区间中，除了 #cf_span[[1; 3]]、#cf_span[[1; 4]]、#cf_span[[1; 5]]、#cf_span[[1; 6]]、#cf_span[[2; 6]]、#cf_span[[3; 6]]、#cf_span[[4; 6]] 之外都满足条件。第二个示例如下图所示：
**Definitions**
Let $ G = (V, E) $ be an undirected graph with $ n $ vertices and $ m $ edges, where $ V = \{1, 2, \dots, n\} $, and $ G $ contains no edge-simple cycles of even length.
Let $ \mathcal{Q} = \{ (l_i, r_i) \mid i \in \{1, \dots, q\} \} $ be a set of $ q $ queries, where each query is a segment $ [l_i, r_i] \subseteq V $.
For any subsegment $ [x, y] \subseteq [l_i, r_i] $, let $ G_{x,y} = (V_{x,y}, E_{x,y}) $ denote the induced subgraph of $ G $ on vertex set $ V_{x,y} = \{x, x+1, \dots, y\} $, with edge set $ E_{x,y} = \{ (u,v) \in E \mid u,v \in V_{x,y} \} $.
**Constraints**
1. $ 1 \leq n, m \leq 3 \cdot 10^5 $
2. $ 1 \leq q \leq 3 \cdot 10^5 $
3. For each query $ (l_i, r_i) $: $ 1 \leq l_i \leq r_i \leq n $
4. $ G $ has no even-length edge-simple cycles.
**Objective**
For each query $ (l_i, r_i) $, compute:
$$
\left| \left\{ [x, y] \mid l_i \leq x \leq y \leq r_i \text{ and } G_{x,y} \text{ is bipartite} \right\} \right|
$$