English · Original
Chinese · Translation
Formal · Original
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 = |V| $ vertices and $ m = |E| $ edges, where $ V = \{1, 2, \dots, n\} $.
Assume $ G $ contains no edge-simple cycle of even length.
For any subsegment $ [x, y] \subseteq [1, n] $, define $ G_{[x,y]} = (V_{[x,y]}, E_{[x,y]}) $ as 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 \le n, m \le 3 \cdot 10^5 $
2. $ G $ has no even-length edge-simple cycles.
3. $ 1 \le q \le 3 \cdot 10^5 $
4. Each query is a segment $ [l_i, r_i] $ with $ 1 \le l_i \le r_i \le n $.
**Objective**
For each query $ [l, r] $, compute:
$$
\left| \left\{ [x, y] \mid l \le x \le y \le r \text{ and } G_{[x,y]} \text{ is bipartite} \right\} \right|
$$
API Response (JSON)
{
"problem": {
"name": "C. Bipartite Segments",
"description": {
"content": "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. Le",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF901C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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. Le...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "你被给定一个无向图，包含 #cf_span[n] 个顶点。图中不存在边简单偶环，即不存在经过每条边至多一次的偶数长度环。我们将顶点编号为 #cf_span[1] 到 #cf_span[n]。\n\n你需要回答 #cf_span[q] 个查询。每个查询由一个顶点区间 #cf_span[[l; r]] 描述，你需要计算其子区间 #cf_span[[x; y]]（#cf_span[l ≤ x ≤ y ≤ r...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ G = (V, E) $ be an undirected graph with $ n = |V| $ vertices and $ m = |E| $ edges, where $ V = \\{1, 2, \\dots, n\\} $. \nAssume $ G $ contains no edge-simple cycle of even leng...",
"is_translate": false,
"language": "Formal"
}
]
}