def is_graph_bipartite_brute_force(graph):
    number_of_nodes = len(graph)

    # Try every possible coloring of the graph with two colors.
    for i in range(2**number_of_nodes):
        coloring = {}

        # Assign colors based on the current bitmask 'i'.
        for node_index in range(number_of_nodes):
            if (i >> node_index) & 1:
                coloring[node_index] = 0 # Color 0
            else:
                coloring[node_index] = 1 # Color 1

        is_bipartite = True

        # Check if the current coloring is valid.
        for node in range(number_of_nodes):

            #Iterate to all neighbors of a given node
            for neighbor in graph[node]:
                #Check color differences. 
                if node in coloring and neighbor in coloring and coloring[node] == coloring[neighbor]:
                    is_bipartite = False
                    break

            if not is_bipartite:
                break

        #If any coloring is bipartite, we're done
        if is_bipartite:
            return True

    return False

def is_bipartite(graph):
    number_of_nodes = len(graph)
    node_colors = [0] * number_of_nodes

    def bfs(start_node):
        queue = [start_node]
        node_colors[start_node] = 1 # Assign the starting node a color.

        while queue:
            current_node = queue.pop(0)

            for neighbor_node in graph[current_node]:
                if node_colors[neighbor_node] == 0:
                    node_colors[neighbor_node] = -node_colors[current_node]

                    # Add to the queue for further exploration.
                    queue.append(neighbor_node)
                elif node_colors[neighbor_node] == node_colors[current_node]:
                    return False # Conflict: not bipartite.

        return True

    # Handle disconnected graphs.
    for node in range(number_of_nodes):
        if node_colors[node] == 0:
            if not bfs(node):
                return False

    # If no conflicts were found, the graph is bipartite.
    return True