Social Network with Snapshots

Design a social-network service that supports adding bidirectional friendships between users and taking point-in-time snapshots of the entire friendship graph so that the state can later be restored exactly. You will implement a class SocialNetworkWithSnapshots that provides the following API:

• add_friendship(user1: int, user2: int) -> None – make user1 and user2 friends. If either user does not exist yet, they are implicitly created. Friendships are symmetric: adding (u,v) also adds (v,u). Duplicate adds are idempotent.
• remove_friendship(user1: int, user2: int) -> None – delete the friendship edge in both directions; no-op if the edge does not exist.
• snapshot() -> int – capture a deep copy of the current friendship graph and return a monotonically increasing integer snap_id that identifies this snapshot.
• restore(snapshot_id: int) -> None – roll the friendship graph back to the exact state captured by the given snapshot_id. All later snapshots remain valid and unchanged. If snapshot_id does not exist, raise an exception.
• get_friends(user: int) -> List[int] – return the sorted list of friends of user; return empty list if the user has no friends or does not exist.

The system must efficiently support an unbounded number of users and snapshots, with the usual constraints of a phone-screen coding exercise (tens of thousands of operations in < 1 s).