Two Teams — Solution & Editorial

Back to the Problem

2-color with BFS: neighbours get the opposite color; a same-color edge proves an odd cycle. Run from every component.

Complexity: O(N + M)

Watch out: Self-loops make it instantly non-bipartite, and disconnected graphs need every component colored.