Statement

You are given an undirected graph G with N vertices and M edges. The edges are numbered from 0 to M - 1, and edge i (0 ≤ i < M) connects vertices a_i and b_i. The graph does not contain self-loops, i.e., a_i ≠ b_i for all i. A partial graph G' of G is a graph obtained by selecting a subset of the edges of G. In particular, for any 0 ≤ l ≤ r < M, we define PG(l, r) as the partial graph containing all edges with indices between l and r, inclusive. A graph is called bipartite if its vertex set can be partitioned into two subsets A and B such that there are no edges between any two vertices within the same subset. Your task is to count the number of bipartite partial graphs of the form PG(l, r). Formally, compute \sum_l = 0^M - 1 \sum_r = l^M - 1 F(l, r), where F(l, r) = 1 if PG(l, r) is bipartite, and F(l, r) = 0 otherwise.