{"problem":{"name":"E. 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":"CF902E"},"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. Let's enumerate vertices from 1 to _n_.\n\nYou 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.\n\n## Input\n\nThe 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.\n\nThe 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.\n\nThe next line contains a single integer _q_ (1 ≤ _q_ ≤ 3·105) — the number of queries.\n\nThe 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.\n\n## Output\n\nPrint _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.\n\n[samples]\n\n## Note\n\nThe first example is shown on the picture below:\n\n![image](https://espresso.codeforces.com/318d2406e6eda825e4828c92499cdf332148286a.png)\n\nFor the first query, all subsegments of \\[1; 3\\], except this segment itself, are suitable.\n\nFor the first query, all subsegments of \\[4; 6\\], except this segment itself, are suitable.\n\nFor 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\\].\n\nThe second example is shown on the picture below:\n\n![image](https://espresso.codeforces.com/653ddd1ad153020bf26d7288369e8fa95b6511cd.png)","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]）的个数，使得当仅保留区间 #cf_span[[x; y]] 中的顶点（包括 #cf_span[x] 和 #cf_span[y]）以及它们之间的边时，所得子图是二分图。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 3·105]，#cf_span[1 ≤ m ≤ 3·105]），分别表示图的顶点数和边数。\n\n接下来的 #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] 之间有一条边。保证该图不含边简单偶环。\n\n接下来一行包含一个整数 #cf_span[q]（#cf_span[1 ≤ q ≤ 3·105]），表示查询数量。\n\n接下来的 #cf_span[q] 行包含查询。第 #cf_span[i] 行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li ≤ ri ≤ n]），表示查询参数。\n\n请输出 #cf_span[q] 个数，每个数占一行：第 #cf_span[i] 个数应为满足条件的子区间 #cf_span[[x; y]]（#cf_span[li ≤ x ≤ y ≤ ri]）的数量，即仅包含区间 #cf_span[[x; y]] 中顶点及其之间边的子图是二分图。\n\n第一个示例如下图所示：\n\n对于第一个查询，区间 #cf_span[[1; 3]] 的所有子区间中，除了其自身以外都满足条件。\n\n对于第一个查询，区间 #cf_span[[4; 6]] 的所有子区间中，除了其自身以外都满足条件。\n\n对于第三个查询，区间 #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]] 之外都满足条件。\n\n第二个示例如下图所示：\n\n## Input\n\n第一行包含两个整数 #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]），表示查询参数。\n\n## Output\n\n请输出 #cf_span[q] 个数，每个数占一行：第 #cf_span[i] 个数应为满足条件的子区间 #cf_span[[x; y]]（#cf_span[li ≤ x ≤ y ≤ ri]）的数量，即仅包含区间 #cf_span[[x; y]] 中顶点及其之间边的子图是二分图。\n\n[samples]\n\n## Note\n\n第一个示例如下图所示：对于第一个查询，区间 #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]] 之外都满足条件。第二个示例如下图所示：","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ 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.  \n\nLet $ \\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 $.  \n\nFor 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} \\} $.  \n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 3 \\cdot 10^5 $  \n2. $ 1 \\leq q \\leq 3 \\cdot 10^5 $  \n3. For each query $ (l_i, r_i) $: $ 1 \\leq l_i \\leq r_i \\leq n $  \n4. $ G $ has no even-length edge-simple cycles.  \n\n**Objective**  \nFor each query $ (l_i, r_i) $, compute:  \n$$\n\\left| \\left\\{ [x, y] \\mid l_i \\leq x \\leq y \\leq r_i \\text{ and } G_{x,y} \\text{ is bipartite} \\right\\} \\right|\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF902E","tags":["data structures","dfs and similar","graphs"],"sample_group":[["6 6\n1 2\n2 3\n3 1\n4 5\n5 6\n6 4\n3\n1 3\n4 6\n1 6","5\n5\n14"],["8 9\n1 2\n2 3\n3 1\n4 5\n5 6\n6 7\n7 8\n8 4\n7 2\n3\n1 8\n1 4\n3 8","27\n8\n19"]],"created_at":"2026-03-03 11:00:39"}}