"""
class UndirectedGraphNode:
     def __init__(self, x):
         self.label = x
         self.neighbors = []
"""
from collections import deque


class Solution:
    """
    @param node: A undirected graph node
    @return: A undirected graph node
    """
    def cloneGraph(self, node):
        # write your code here
        if not node:
            return None
        
        def copy_graph_nodes(node):
            nodes = {}
            seen = {node}
            q = deque([node])
            while q:
                n = q.popleft()
                new_node = UndirectedGraphNode(n.label)
                nodes[n] = new_node
                for neighbor in n.neighbors:
                    if neighbor not in seen:
                        seen.add(neighbor)
                        q.append(neighbor)
            
            return nodes
        
        def build_dir(node, nodes):
            q = deque([node])
            seen = {node}
            while q:
                n = q.popleft()
                for neighbor in n.neighbors:
                    nodes[n].neighbors.append(nodes[neighbor])
                    if neighbor not in seen:
                        seen.add(neighbor)
                        q.append(neighbor)
                        
                        
        nodes = copy_graph_nodes(node)
        build_dir(node, nodes)
        
        return nodes[node]