Clone Graph

Problem Statement

Given a reference to the root of a graph where each node has a reference to a unique node in the graph, you're tasked with creating a "clone" of this graph by performing a deep copy of all its nodes. This means that each node in the new graph should be an exact copy of its corresponding node in the original graph, including edge connections.

Rules and Constraints

• Graph nodes may contain any number of references to other nodes in the graph.
• A graph node can be null, and if so, its clone should also be null.
• A new graph with the same structure as the original graph should be created, and this new graph should be separate from the original graph.
• The function should be able to handle graphs with any number of nodes and edges.
• The time complexity of the solution should be acceptable, i.e., it should not be prohibitively expensive in terms of the number of operations it performs.

Requirements

The function should take a reference to the root of the original graph and return a reference to the root of the cloned graph. The clone should be an exact replica of the original graph, including all nodes and edges.

Example

Input: {"input_data":[1,2,3]} Output: [1,2,3]