#!/usr/bin/env python3

__author__ = 'Wei Mu'

"""
# Definition for a Node.
class Node:
    def __init__(self, val, neighbors):
        self.val = val
        self.neighbors = neighbors
"""
class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        node_list = [None] * 101
        stack = [node]
        
        while stack != []:
            cur_node = stack.pop(0)
            
            if node_list[cur_node.val] == None:
                node_list[cur_node.val] = Node(cur_node.val, [])
            
            for neighbor_node in cur_node.neighbors:
                if node_list[neighbor_node.val] == None:
                    stack.append(neighbor_node)
        
        visited = []
        stack = [node]
        
        while stack != []:
            cur_node = stack.pop(0)
            visited.append(cur_node)
            
            cur_val, cur_neighbors = [cur_node.val, cur_node.neighbors]
            
            for neighbor_node in cur_neighbors:
                print(cur_val, neighbor_node.val)
                node_list[cur_val].neighbors.append(node_list[neighbor_node.val])
                if neighbor_node not in visited and neighbor_node not in stack:
                    stack.append(neighbor_node)
        
        return node_list[node.val]
            
