class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        from collections import defaultdict, deque
        neighborList = defaultdict(list) #ϣڼ¼ϽھӵĹϵ, keyÿϽ㣬valneighbors
        mapping = dict() #ϣڼ¼ϽӦ½ڵ
        
        def bfs(queue):
            if not queue:
                return
            newqueue = deque()
            
            while queue:
                cur = queue.popleft()
                mapping[cur] = Node(cur.val, []) #ΪÿϽ㴴һӦ½ڵ
                for nei in cur.neighbors:
                    neighborList[cur].append(nei) #¼µǰϽھ
                    if nei not in visited:
                        visited.add(nei)
                        newqueue.append(nei)
            bfs(newqueue) #BFSһ
         
        visited = {node}           
        q = deque()
        q.append(node)
        bfs(q)
        visited = {node}
        
        def generate(queue):
            while queue:
                newqueue = []
                for node in queue:
                    if node:                
                        if not neighborList[node]: #ûھ
                            return

                        for nei in neighborList[node]: #ÿھ
                            mapping[node].neighbors.append(mapping[nei]) #µĽǡϽھӶӦġ½
                            if nei not in visited:
                                visited.add(nei)
                                newqueue.append(nei)
                queue = newqueue[:]

        generate([node])

        return mapping[node] #Ӧ½ڵ