class Solution:
    #O(|E|+|V|) time complexity
    def isBipartite(self, graph: List[List[int]]) -> bool:
        
        #we can use graph coloring method here.
        #use BFS to traverse each node and for each neighbour assigned different color than its parent
        #Start with two colors and if we find anywhere the neighbor is already having same color then its not bipartite 
        #Since the graph is not necessarily connected we may have more than one componets too
        
        
        colorA = 'A' 
        colorB = 'B'
        queue=[]
        
        colorDict = {}
        for i in range(len(graph)):
            if i not in colorDict.keys():
                colorDict[i]=colorA
            queue.append(i)
            while (queue):
                node = queue.pop(0)
                for neigh in graph[node]:
                    # print(neigh,colorDict,queue)
                    if colorDict.get(neigh)==colorDict[node]:
                        return False
                    elif neigh not in colorDict.keys():
                        colorDict[neigh] = colorA if colorDict[node]!=colorA else colorB
                        iscolorused=True
                        queue.append(neigh)
                    else:
                        continue
           
        return True