Clone graph: deep-copy a connected undirected graph

Given one node of a connected undirected graph, return a deep copy of the whole graph: new node objects with the same values and the same edges, each neighbor list in the same order as in the original. The problem can come wrapped in a domain story (people and their contacts, services and their dependencies); recognize the graph copy underneath.

Interface

Unless you agree on a different interface with the interviewer, assume:

class Node: val: int; neighbors: list[Node].
clone_graph(node: Node | None) -> Node | None returns the copy of node, or None for an empty graph.

For testing, a graph with nodes 1..n is written as an adjacency list where entry i holds the neighbors of node i + 1.

Example

[[2, 4], [1, 3], [2, 4], [1, 3]]  ->  [[2, 4], [1, 3], [2, 4], [1, 3]]   # a 4-cycle, every node new
[[]]                              ->  [[]]                               # one node, no edges
[]                                ->  []                                 # empty graph

Constraints

0 <= n <= 100; values are unique and in 1..n.
The graph is undirected and connected; no duplicate edges or self-loops.

Clarifying questions

Are node values unique, or can two nodes share a value?
Is the graph always connected, or should I copy every component?
Can there be self-loops or duplicate edges?
Must neighbor order be preserved?

What a strong answer covers

A map from original node to its copy, filled during BFS or DFS: create the copy the first time a node is seen, then append copied neighbors in order. O(V + E) time and O(V) memory.
Why the map matters: without it, cycles loop forever and shared neighbors are duplicated.
An iterative version if the graph can be deep.
A test that checks the copy shares no node objects with the original and has the same edges.

Follow-ups

The graph is directed and may have several components; copy all of it from a list of nodes.
Nodes also carry a random pointer to any node (copy list with random pointer, generalized).
Serialize the graph to a string and back.