class Solution:

    # Solution-1: DFS with recursion
    def cloneGraph_solution_1(self, node: 'Node') -> 'Node':
        # key is original node, value is new node
        # each time a node is visited, do the following thing:
        #   1. copy this node as node_cp, add node --> node_cp to self.visited
        #   2. build the pointer from node_cp to child_cp, where child_cp is the copy of neighbors of node.
        # 难点：edge是双向的，每次visit到的node，只需要构建这个node指向neighbors的指针即可，不然会重复。
    
        visited = dict()

        def dfs(node: 'Node', visited:dict):
            if not node: return None
            if node in visited:
                return visited[node]
            visited[node] = Node(node.val)
            for neighbor in node.neighbors:
                visited[node].neighbors.append(dfs(neighbor, visited))
            return visited[node]
        
        return dfs(node, visited)
    
    
    # Solution-2: DFS with iteration and stacks
    def cloneGraph_solution_2(self, node: 'Node') -> 'Node':

        if not node: return None

        node_cp = Node(node.val)
        visited = {node:node_cp}
        
        stack = [node]
        while stack:
            
            node = stack.pop()
            print(node.val)
            for neighbor in node.neighbors:
                if neighbor not in visited:
                    visited[neighbor] = Node(neighbor.val)
                    stack.append(neighbor)
                visited[node].neighbors.append(visited[neighbor])
        return node_cp

    # Solution-3: BFS with Queue
    def cloneGraph_solution_3(self, node: 'Node') -> 'Node':

        if not node: return None

        node_cp = Node(node.val)
        visited = {node:node_cp}
        
        from collections import deque
        Q = deque([node])
        while Q:
            print([i.val for i in Q])
            node = Q.popleft()
            print(node.val)
            for neighbor in node.neighbors:
                if neighbor not in visited:
                    visited[neighbor] = Node(neighbor.val)
                    Q.append(neighbor)
                visited[node].neighbors.append(visited[neighbor])
        return node_cp
    
    def cloneGraph(self, node: 'Node') -> 'Node':
        return self.cloneGraph_solution_1(node)