Clone Graph

You get node 1 of an undirected graph. The graph has n nodes with the values 1 to n. Each Node holds its value and a list of its neighbors. Its class is in the starter code.

Make a deep copy of the whole graph, and return the copy's node 1:

• Make n new nodes, one per original node, with the same values.
• Give each new node the copies of the original's neighbors, in the same order.
• Never put an original node into the copy.

An empty graph (n = 0) comes as None. Return None for it.

The examples write a graph as adjacency lists. Entry i - 1 of adjList lists the values of node i's neighbors. The tests walk your copy from the node you return. They print each node's neighbors. They also flag any node that belongs to the original graph.

Example 1:

Input: adjList = [[2, 3], [1, 3], [1, 2, 4], [3, 5], [4]]
Output: [[2, 3], [1, 3], [1, 2, 4], [3, 5], [4]]
Explanation: Five nodes: a triangle with a tail.
    1 - 2
     \ /
      3 - 4 - 5
The copy has the same shape, built from 5 new nodes.

Example 2:

Input: adjList = [[2], [1]]
Output: [[2], [1]]
Explanation: Two nodes joined by one edge.
Each new node lists the other new node.

Example 3:

Input: adjList = [[3], [3], [1, 2]]
Output: [[3], [3], [1, 2]]
Explanation: Node 2 is not a neighbor of node 1.
The copy reaches it only through node 3.

Constraints:

• 0 to 50,000 nodes.
• Node i has the value i.
• Up to 100,000 edges.
• No edge joins a node to itself.
• No two edges join the same two nodes.
• Every node can be reached from node 1.