The Temporal Graph

Prompt

You are given an undirected graph with \(N\) vertices, initially containing no edges. A sequence of \(Q\) operations occurs. Each operation is one of the following: - + u v: Add an edge between vertices \(u\) and \(v\). - - u v: Remove an existing edge between vertices \(u\) and \(v\). - ? u v: Determine whether \(u\) and \(v\) are connected. - B u: Determine whether the connected component containing \(u\) is bipartite. - S u: Report the number of vertices in the connected component containing \(u\). - C: Report the total number of connected components. Every edge insertion is guaranteed to involve an absent edge, and every removal involves an existing edge. Your task is to process all operations in their original order. However, there is a catch. Performance requirement Your solution must handle up to \(200{,}000\) vertices and \(200{,}000\) operations without recomputing the graph from scratch after each update. Input Format The first line contains two integers: N Q The next \(Q\) lines each contain one operation in the format described above. Constraints \[ 1\le N,Q\le 2\times 10^5 \] \[ 1\le u,v\le N,\qquad u\ne v \] Time limit: 5 seconds Memory limit: 512 MB Example Input 5 15 + 1 2 + 2 3 ? 1 3 B 1 + 1 3 B 2 S 1 C - 1 3 B 1 - 2 3 ? 1 3 S 2 C ? 4 5 Output YES YES NO 3 3 YES NO 2 4 NO