from collections import deque
from structures import GraphNode

def clone_graph(root):
    if root is None:
        return None
    copies = {root: GraphNode(root.val)}
    queue = deque([root])
    while queue:
        original = queue.popleft()
        for neighbor in original.neighbors:
            if neighbor not in copies:
                copies[neighbor] = GraphNode(neighbor.val)
                queue.append(neighbor)
            copies[original].neighbors.append(copies[neighbor])
    return copies[root]