text: """
  Clone an undirected graph. Each node in the graph contains a label and a list
  of its neighbors.
  
  
  OJ's undirected graph serialization:
  Nodes are labeled uniquely.
  
  We use # as a separator for each node, and , as a separator for node label and
  each neighbor of the node.
  As an example, consider the serialized graph {0,1,2#1,2#2,2}.
  
  The graph has a total of three nodes, and therefore contains three parts as
  separated by #.
  
  First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
  Second node is labeled as 1. Connect node 1 to node 2.
  Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a
  self-cycle.
  Visually, the graph looks like the following:
  
         1
        / \
       /   \
      0 --- 2
           / \
           \_/
  """
  
  
  # Definition for a undirected graph node
  # class UndirectedGraphNode:
  #     def __init__(self, x):
  #         self.label = x
  #         self.neighbors = []
  
  
  # BFS
  def cloneGraph1(self, node):
      if not node:
          return
      nodeCopy = UndirectedGraphNode(node.label)
      dic = {node: nodeCopy}
      queue = collections.deque([node])
      while queue:
          node = queue.popleft()
          for neighbor in node.neighbors:
              if neighbor not in dic: # neighbor is not visited
                  neighborCopy = UndirectedGraphNode(neighbor.label)
                  dic[neighbor] = neighborCopy
                  dic[node].neighbors.append(neighborCopy)
                  queue.append(neighbor)
              else:
                  dic[node].neighbors.append(dic[neighbor])
      return nodeCopy
  
  # DFS iteratively
  def cloneGraph2(self, node):
      if not node:
          return
      nodeCopy = UndirectedGraphNode(node.label)
      dic = {node: nodeCopy}
      stack = [node]
      while stack:
          node = stack.pop()
          for neighbor in node.neighbors:
              if neighbor not in dic:
                  neighborCopy = UndirectedGraphNode(neighbor.label)
                  dic[neighbor] = neighborCopy
                  dic[node].neighbors.append(neighborCopy)
                  stack.append(neighbor)
              else:
                  dic[node].neighbors.append(dic[neighbor])
      return nodeCopy
  
  # DFS recursively
  def cloneGraph(self, node):
      if not node:
          return
      nodeCopy = UndirectedGraphNode(node.label)
      dic = {node: nodeCopy}
      self.dfs(node, dic)
      return nodeCopy
  
  def dfs(self, node, dic):
      for neighbor in node.neighbors:
          if neighbor not in dic:
              neighborCopy = UndirectedGraphNode(neighbor.label)
              dic[neighbor] = neighborCopy
              dic[node].neighbors.append(neighborCopy)
              self.dfs(neighbor, dic)
          else:
              dic[node].neighbors.append(dic[neighbor])
  