Two-Colorable Graph

You are given an undirected graph with n nodes numbered 0 to n - 1, described by an adjacency list graph, where graph[u] is the list of nodes adjacent to node u. The graph is guaranteed to satisfy:

• There are no self-edges (graph[u] never contains u).
• There are no repeated edges (graph[u] has no duplicate values).
• The adjacency is symmetric: if v appears in graph[u], then u appears in graph[v].
• The graph may be disconnected.

Determine whether every node can be assigned one of two colors so that no edge joins two nodes of the same color. Equivalently, the nodes can be split into two groups A and B such that every edge connects a node in A to a node in B.

Return true if such a two-coloring exists, and false otherwise.

Examples

Example 1

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: Nodes 0, 1, 2 are mutually adjacent (0-1, 1-2, 0-2), forming a triangle. A triangle cannot be split into two groups with no edge inside a group, so no valid two-coloring exists.

Example 2

Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Explanation: Place nodes 0 and 2 in one group and nodes 1 and 3 in the other. Every edge (0-1, 1-2, 2-3, 3-0) then connects the two groups.