Is Graph Bipartite?

Given an undirected graph represented as an adjacency list, where graph[i] is a list of nodes that node i is connected to, return true if and only if the graph is bipartite.

A graph is bipartite if the nodes can be partitioned into two sets such that no two adjacent nodes belong to the same set. Equivalently, the graph can be colored with two colors so that every edge connects nodes of different colors.

Examples

Example 1:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]

Output: false

Explanation: There is no way to partition the nodes into two groups such that every edge connects nodes from different groups. For instance, nodes 0, 1, and 2 are all mutually connected, forming a triangle (odd cycle), which makes the graph non-bipartite.

Example 2:

Input: graph = [[1,3],[0,2],[1,3],[0,2]]

Output: true

Explanation: We can partition the nodes into two sets: {0, 2} and {1, 3}. Every edge connects a node from one set to a node in the other set.

Example 3:

Input: graph = [[],[2,4,6],[1,4,8,9],[7,8],[1,2,8,9],[6,9],[1,5,7,8,9],[3,6,9],[2,3,4,6,9],[2,4,5,6,7,8]]

Output: false

Explanation: The graph contains an odd-length cycle, making it impossible to 2-color without a conflict.

Constraints

• graph.length == n
• 1 <= n <= 100
• 0 <= graph[i].length < n
• 0 <= graph[i][j] <= n - 1
• graph[i][j] != i (no self-loops)
• If graph[i] contains j, then graph[j] contains i (undirected)
• The graph may be disconnected