1604 - Bipartite Graph
Time Limit : 5 Second
Memory Limit : 64 MB
Bipartite graph (or bigraph, http://en.wikipedia.org/wiki/Bipartite_graph) is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in A to one in V; there are no edges connect two vertices both in U and V.
In this problem, you need to simulate a Bipartite Graph Judging Machine(BGJM). The BGJM can accept two kinds of operations:
1. ADD X1 X2 It means we add a bidirectional edge (X1, X2) to the graph.
2. CHECK Judge the graph, If the graph is Bipartite Graph, print “YES”. Otherwise, print “NO”.
Initially, the graph contains N vertices and no edges, of course, it’s a bigraph.
Multiple test cases, for each test case:
The first line contain two numbers N and Q. It means there are N vertices in the graph and you need to simulate Q operations.
1 <= N, Q <= 3 * 10^5
Next Q lines each line contains an operation. The format is mentioned above.
For each “CHECK” operation, you need to print the result in a line.
- sample input
3 6 ADD 1 2 CHECK ADD 2 3 CHECK ADD 1 3 CHECK
- sample output
YES YES NO