Still Two Teams?

Difficulty: 1850 4000 ms 128 MB

graphs union-find

Edges arrive one by one. After each edge, print whether the graph built SO FAR is still bipartite (once it stops being bipartite it stays that way).

Input: the first line has N and M; each of the next M lines has an edge u v.

Output: M lines of YES/NO.

Constraints:

• 1 ≤ N, M ≤ 10⁵

Sample Tests

3 3
1 2
2 3
1 3

YES
YES
NO

2 2
1 2
1 2

YES
YES

Read the Editorial