class UndirectedGraphNode {
  int label;
  ArrayList<UndirectedGraphNode> neighbors;
  public UndirectedGraphNode(int label) {
   this.label = label;
   neighbors = new ArrayList<UndirectedGraphNode>();
 }
}
 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        // write your code here
       HashMap<Integer, UndirectedGraphNode> map = new HashMap<>();
       return dfs(node, map);
    }
    public UndirectedGraphNode dfs(UndirectedGraphNode node, HashMap<Integer, UndirectedGraphNode> map) {
        if (node == null) return null;

        if (map.containsKey(node.label)){
            return map.get(node.label);
        } else {
            UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
            map.put(node.label, clone);
            for (UndirectedGraphNode neig : node.neighbors){
                clone.neighbors.add(dfs(neig, map));
            }
            return clone;
        }
    }