Snapshot Social Network Follow System

Problem Description Design a social network follow system that supports historical version queries. A follow relationship is directed. For example, follow(1, 2) means user 1 follows user 2, but not necessarily the other way around. The system starts at version 0. All Follow and Unfollow operations are written to the current version. A new version is created only when CreateSnapshot() is called: it returns the current version number, then increments the current version by 1. Implement the following APIs: Follow(followerId, followeeId) User followerId follows user followeeId, written to the current version. Unfollow(followerId, followeeId) User followerId unfollows user followeeId, written to the current version. CreateSnapshot() int Creates a snapshot, returns the current version number, and then increments the current version. IsFollowing(followerId, followeeId, snapId) bool Returns whether user followerId follows user followeeId at version snapId. Example sn.Follow(1, 2) // writes to version 0 sn.CreateSnapshot() // returns 0, current version becomes 1 sn.Unfollow(1, 2) // writes to version 1 sn.IsFollowing(1, 2, 0) // true sn.IsFollowing(1, 2, 1) // false Input / Output Format For online judge purposes, use the following format: The first line contains an integer Q, the number of operations. Each of the next Q lines is one of the following commands: Follow followerId followeeId Unfollow followerId followeeId CreateSnapshot IsFollowing followerId followeeId snapId Output: Follow and Unfollow produce no output. CreateSnapshot outputs the returned version number. IsFollowing outputs true or false. Constraints 1 <= Q <= 2 * 10^5 1 <= followerId, followeeId <= 10^9 0 <= snapId <= current version Within the same version, the same pair of users may be followed/unfollowed multiple times. The final state in that version is determined by the last operation in that version. Example Input 5 Follow 1 2 CreateSnapshot Unfollow 1 2 IsFollowing 1 2 0 IsFollowing 1 2 1 Output 0 true false