983. Check if Graph is Bipartite

Given an undirected graph with n nodes and a list of edges, determine whether it is bipartite — whether its nodes can be split into two groups so that every edge connects nodes in different groups (equivalently, it has no odd-length cycle). Return true or false. The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Boolean — true or false.

Examples

Input: {"n":4,"edges":[[0,1],[1,2],[2,3],[3,0]]}
Output: true
Explanation: Even cycle is bipartite.

Input: {"n":3,"edges":[[0,1],[1,2],[2,0]]}
Output: false
Explanation: Odd cycle is not bipartite.

Input: {"n":2,"edges":[[0,1]]}
Output: true
Explanation: Single edge.

Constraints

• 1<=n<=10^5
• undirected

Asked by