Clone Undirected Graph

Problem Statement

You are given a reference to a node in a connected undirected graph. Each node contains a number (int) and a list of its adjacent nodes. Your task is to create and return a deep copy of this graph, such that the cloned graph has the exact same structure as the original.

Examples

Example 1:
Input:
{
  "id": "1",
  "neighbors": [
    {
      "id": "2",
      "neighbors": [
        {"ref": "1"},
        {
          "id": "3",
          "neighbors": [
            {"ref": "2"},
            {
              "id": "4",
              "neighbors": [
                {"ref": "3"},
                {"ref": "1"}
              ],
              "val": 4
            }
          ],
          "val": 3
        }
      ],
      "val": 2
    },
    {"ref": "4"}
  ],
  "val": 1
}

Explanation:
Node 1 has value 1 and is connected to nodes 2 and 4.
Node 2 has value 2 and is connected to nodes 1 and 3.
Node 3 has value 3 and is connected to nodes 2 and 4.
Node 4 has value 4 and is connected to nodes 3 and 1.

Example 2:
Input:
{
  "id": "5",
  "neighbors": [
    {
      "id": "6",
      "neighbors": [
        {"ref": "5"}
      ],
      "val": 6
    }
  ],
  "val": 5
}

Explanation:
Node 5 has value 5 and is connected to node 6.
Node 6 has value 6 and is connected back to node 5.
    

Constraints

• The total number of nodes is between 1 and 120.
• The graph is undirected and simple (no self loops or duplicate edges).
• If node A is a neighbor of node B, then node B is also a neighbor of node A.
• You must return the cloned node that corresponds to the input node.