Is the Graph Bipartite?

A graph with n nodes and undirected edges is bipartite if the nodes can be split into two groups so that every edge joins a node of one group to a node of the other (no edge inside a group). Return True if the graph is bipartite. The graph may have several components.

A triangle is not bipartite; a square is.

Examples

Example 1

Input:

is_bipartite(4, [[0, 1], [1, 2], [2, 3], [3, 0]])

Output:

True

Example 2

Input:

is_bipartite(3, [[0, 1], [1, 2], [2, 0]])

Output:

False

Constraints

• 0 <= n <= 100000
• 0 <= len(edges) <= 200000
• No node has an edge to itself unless the graph is not bipartite.