Dynamic Bipartite Graph Checking

Given a graph with (n) nodes. Over (k) time units, (m) edges will appear and then disappear. Each edge is specified by two nodes (u) and (v) along with an active time interval ([L, R]), i.e., it is present for every time (t) satisfying (L \le t \le R). For each time unit from (1) to (k), determine whether the graph formed by all active edges is bipartite.

A graph is bipartite if its set of nodes can be partitioned into two disjoint sets such that every edge connects a node in one set with a node in the other set.

Original Problem: BZOJ4025.

inputFormat

The first line contains three integers (n), (k), and (m), where (n) is the number of nodes, (k) is the number of time units, and (m) is the number of edges. Each of the next (m) lines contains four integers (u), (v), (L), and (R), indicating that an edge between nodes (u) and (v) exists during the time interval ([L, R]).

outputFormat

Output (k) lines. The (i)th line should contain the string YES if the graph at time (i) is bipartite, or NO otherwise.

sample

3 3 2
1 2 1 3
2 3 2 2

YES
YES
YES