Social Network Follow/Unfollow With Snapshots

You are to implement a simplified social network with snapshot queries. Implement the following APIs: follow(int a, int b): user a follows user b. unfollow(int a, int b): user a unfollows user b. int snap(): create and return a new snapshot id snapId (starting from 0, increasing by 1). bool is_following(int a, int b, int snapId): return whether user a was following user b at the time represented by snapshot snapId. Requirements: You must preserve history so is_following can be queried for any past snapshot. The implementation should be efficient under a large number of operations. Optional stdin/stdout format First line: integer Q (# of operations) Next Q lines: one operation per line: follow a b unfollow a b snap is_following a b snapId Print the generated snapId for each snap. Print true/false for each is_following. Constraints (can be discussed in interview) 1 <= Q <= 2e5 User ids are non-negative integers (assume up to 1e9). Example Input: 9 follow 1 2 snap is_following 1 2 0 unfollow 1 2 is_following 1 2 0 snap is_following 1 2 1 is_following 1 2 0 Output: 0 true true 1 false true Example Input 9 follow 1 2 snap is_following 1 2 0 unfollow 1 2 is_following 1 2 0 snap is_following 1 2 1 is_following 1 2 0 Output 0 true true 1 false true