class Solution:
    '''
    [[1,2,3], [0,2], [0,1,3], [0,2]]
    [[],[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]]
    [[1, 3],[0, 2],[1, 3],[0, 2]]
    '''
    def verify_bipartite_graph(self, graph, group_dict, curr_id, group_id):

        group_dict[group_id].add(curr_id)

        for neighbor in graph[curr_id]:
            if neighbor in group_dict[group_id]:
                return False # same color
            if neighbor not in group_dict[-1 * group_id]: # unvisited , paint opposite color
                if not self.verify_bipartite_graph(graph, group_dict, neighbor, -1 * group_id):
                    return False

        # visited = len(group_dict[1]) + len(group_dict[-1])
        # return visited == len(graph)
        return True

    def isBipartite(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: bool
        """
        groups = {1 : set(), -1 : set()}
        #return self.verify_bipartite_graph(graph, groups, 0, 1) <- old code
        #--->
        for i in range(len(graph)):
            if not self.verify_bipartite_graph(graph, groups, i, 1):
                return False
        return True
        #<----