func deepCopy(node *Node, copied map[int]*Node) *Node {
	if node == nil {
		return nil
	}
	copied[node.Val] = &Node{
		Val:       node.Val,
		Neighbors: make([]*Node, len(node.Neighbors)),
	}

	for i := 0; i < len(node.Neighbors); i++ {
		if c, found := copied[node.Neighbors[i].Val]; found {
			copied[node.Val].Neighbors[i] = c
			continue
		}
		copied[node.Val].Neighbors[i] = deepCopy(node.Neighbors[i], copied)
	}

	return copied[node.Val]
}

func cloneGraph(node *Node) *Node {
	return deepCopy(node, make(map[int]*Node, 0))
}