#time: O(N**2) - space: O(N)

class Solution:
    def is_bypartite(self, graph):
        colors = dict()
        for node in range(len(graph)):
            if node not in colors[node]:
                colors[node] = 0
            if not self.dfs(node, graph, colors):
                return False
        
        return True
    
    def dfs(self, node, graph, colors):
        for nbr in graph[node]:
            if nbr in colors:
                if colors[nbr] == colors[node]:
                    return False
            else:
                colors[nbr] = 1 - colors[node]

                if not self.dfs(nbr, graph, colors):
                    return False
        
        return True
    
    