Clone Graph

A connected undirected graph has nodes 1 … n; each node knows its list of neighbours. Make a deep copy of the graph — new node objects whose neighbour lists point to the new nodes — starting from node 1.

To show that your copy is complete and correctly wired, walk your copy with BFS from node 1 and print every node as you take it out of the queue, together with its neighbour list.

Input:

• line 1: n
• next n lines: line i describes node i: first the number of neighbours d, then the d neighbours in their stored order

Output: n lines in BFS order: v: a b c — the node's value, a colon, then its neighbours in their stored order (just v: if it has none). In BFS, enqueue unvisited neighbours in the stored order.

Constraints: 1 ≤ n ≤ 10⁴, total neighbour entries ≤ 6·10⁴, no self-loops or repeated edges, the graph is connected.

The technique: BFS (or DFS) over the original with a hash map original → copy. When you meet a node for the first time, create its copy; then append the copied neighbour to the current copy's list.