GraphBFSColoring
A graph is bipartite if its nodes can be split into two groups so that every edge connects a node from one group to a node in the other. Decide whether the given undirected graph (which may be disconnected) is bipartite.
Input
Line 1: n and m. Next m lines: u v, an undirected edge (0-based).
Output
Print true if the graph is bipartite, otherwise false.
Constraints
1 <= n <= 2000 0 <= m <= 5000 No self-loops or repeated edges.
Example 1
Input
4 4 0 1 1 2 2 3 3 0
Output
true
An even cycle can be coloured alternately.
Example 2
Input
3 3 0 1 1 2 2 0
Output
false
A triangle is an odd cycle.