{"raw_statement":[{"iden":"statement","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."},{"iden":"input","content":"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.\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."},{"iden":"output","content":"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."},{"iden":"examples","content":"Input\n\n6 6\n1 2\n2 3\n3 1\n4 5\n5 6\n6 4\n3\n1 3\n4 6\n1 6\n\nOutput\n\n5\n5\n14\n\nInput\n\n8 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\n\nOutput\n\n27\n8\n19"},{"iden":"note","content":"The 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)"}],"translated_statement":[{"iden":"statement","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\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\n\n"},{"iden":"input","content":"第一行包含两个整数 #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]）——查询参数。"},{"iden":"output","content":"请输出 #cf_span[q] 个数，每行一个：第 #cf_span[i] 个数应为满足条件的子区间 #cf_span[[x; y]]（#cf_span[li ≤ x ≤ y ≤ ri]）的数量，即仅包含区间 #cf_span[[x; y]] 中顶点及其之间边的子图是二分图。"},{"iden":"examples","content":"输入\n6 6\n1 2\n2 3\n3 1\n4 5\n5 6\n6 4\n3\n1 3\n4 6\n1 6\n输出\n5\n5\n14\n\n输入\n8 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\n输出\n27\n8\n19"},{"iden":"note","content":"第一个例子如下图所示：对于第一个查询，区间 #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]] 外均符合条件。第二个例子如下图所示："}],"sample_group":[],"show_order":[],"formal_statement":"**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 length.  \n\nFor 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]} \\} $.  \n\n**Constraints**  \n1. $ 1 \\le n, m \\le 3 \\cdot 10^5 $  \n2. $ G $ has no even-length edge-simple cycles.  \n3. $ 1 \\le q \\le 3 \\cdot 10^5 $  \n4. Each query is a segment $ [l_i, r_i] $ with $ 1 \\le l_i \\le r_i \\le n $.  \n\n**Objective**  \nFor each query $ [l, r] $, compute:  \n$$\n\\left| \\left\\{ [x, y] \\mid l \\le x \\le y \\le r \\text{ and } G_{[x,y]} \\text{ is bipartite} \\right\\} \\right|\n$$","simple_statement":null,"has_page_source":false}