In this task, you are given a graph with $N$ nodes and $M$ edges. Furthermore, you are required to answer $Q$ queries. In every query, all the edges from the interval $[l_i,r_i]$ are temporarily removed and you should check whether the graph contains an odd cycle or not.

Subtask 1

For every query do a DFS from every node and check if an odd cycle is formed.

Complexity: $\mathcal{O}(QNM)$.

Subtask 2

The graph is bipartite if and only if it contains no odd cycle. Therefore we can color the nodes with two colors (with DFS or BFS) and check if two adjacent nodes share the same color or not.

Complexity: $\mathcal{O}(QM)$.

Subtask 3

We can sort the queries by their right endpoints ($r_i$) and answer them offline. Therefore we insert all the edges in the decreasing order of their indices into a DSU structure.

Complexity: $\mathcal{O}(Q\log Q+M\alpha (N))$.

Subtask 4

We can sort the queries by their left endpoint ($l_i$) and apply our solution from subtask 3 to all queries with the same $l_i$.

Complexity: $\mathcal{O}(Q\log Q+200M\alpha (N))$.

Subtask 5

We use the "Mo's algorithm" technique. Split the range $[1,M]$ of edge indices into blocks of size $B$ and sort the queries by $l_i/B$ or by $r_i$ if their left endpoint is in the same block. We can now keep two pointers to hold the current range of removed edges. If we answer all queries in the current block, the right pointer moves at most $M$ steps. The left pointer moves at most $QB$ steps in total. Since the left pointer may move to the left and the right inside the current block we need to modify our DSU to allow rollbacks. If we choose $B=M/\sqrt{Q}$ we get the following runtime:

Complexity: $\mathcal{O}(Q\log Q+M\sqrt{Q}\log N)$.

Subtask 6

For any $1\le l\le M$, let $last[l]$ be the last index $r$ such that the answer for the query $[l,r]$ is positive (or $M+1$ if no such index exists). That is, the graph excluding the edges $[l,r]$ is bipartite, but the graph excluding the edges $[l,r-1]$ is not. We can prove that if $l_1<l_2$, then $last[l_1]\le last[l_2]$. We will exploit this fact in order to compute the array last using a divide & conquer algorithm.

We write a recursive function $rec$, which takes two intervals: $[l_1,l_2]$, $[r_1,r_2]$ $(1\le l_1\le l_2\le M,1\le r_1\le r_2\le M+1)$, possibly intersecting, but $l_1\le r_1$ and $l_2\le r_2$. This function will compute $last[l]$ for each $l\in [l_1,l_2]$, assuming that for these values of $l$, we have $last[l]\in [r_1,r_2]$. We will initially call $rec([1,M],[1,M+1])$.

We assume that when $rec([l_1,l_2],[r_1,r_2])$ is called, then our DSU contains all edges with indices to the left of $l_1$ and to the right of $r_2$. For instance, when $M=9$ and $rec([2,5],[3,7])$ is called, then edges with indices $1$, $8$, and $9$ should be in the DSU. We also assume that the graph in the DSU is bipartite.

We take $l_{mid}:=\frac{l_1+l_2}{2}$ and compute $last[l_{mid}]$; this can be done by adding all edges $[l_1,l_{mid}-1]$ to the DSU, and then trying to add all edges with indices $r_2,r_2-1,r_2-2,\dots$, until we try to add an edge breaking the bipartiteness. The index $r_{mid}$ of such an edge is exactly $last[l_{mid}]$. We then rollback all edges added so far in our recursive call.

Now that we know that $last[l_{mid}]=r_{mid}$, we will run two recursive calls:

• For each $l\in [l_1,l_{mid}-1]$, we know that $last[l]\in [r_1,r_{mid}]$. We run $rec([l_1,l_{mid}-1],[r_1,r_{mid}])$, remembering to add all necessary edges to the right of $r_{mid}$. After the recursive call, we rollback them.
• For each $l\in [l_{mid}+1,l_2]$, we know that $last[l]\in [r_{mid},r_2]$. We run $rec([l_{mid}+1,l_2],[max(l_{mid}+1,r_{mid}),r_2])$, now adding all necessary edges to the left of $l_{mid}+1$. We rollback them after the recursive call.

We can see that each recursive call uses at most $\mathcal{O}((l_2-l_1)+(r_2-r_1))$ edge additions and rollbacks in DSU, each taking $\mathcal{O}(\log N)$ time pessimistically. Also, on each level of recursion, the total length of all intervals is bounded by $2M$. Hence, all intervals in all recursive calls have total length bounded by $\mathcal{O}(M\log M)$. Hence, the total time of the preprocessing is $\mathcal{O}(M\log M\log N)$.

With our preprocessing, each query $[l,r]$ reduces to simply verifying $r\le last[l]$, which can be done in constant time.

Complexity: $\mathcal{O}(M\log M\log N+Q)$.