1093. DSU with Rollback — Online Connectivity

Process a sequence of operations on a disjoint-set structure over n elements. Each operation is [type, a, b]: type 0 unions a and b; type 1 queries whether a and b are connected (record the boolean); type 2 rolls back the most recent union operation (undoing it if it merged two sets, or doing nothing if that union was a no-op). Return the list of boolean answers to the type-1 queries in order. The input is JSON {n, ops}.

Input: JSON {n, ops} with each op [type, a, b].

Output: Array — booleans for each connectivity query.

Examples

Input: {"n":4,"ops":[[0,0,1],[1,0,1],[0,1,2],[1,0,2],[2,-1,-1],[1,0,2]]}
Output: [true,true,false]
Explanation: Rollback undoes the 1-2 union.

Input: {"n":2,"ops":[[0,0,1],[1,0,1]]}
Output: [true]
Explanation: Union then query.

Input: {"n":3,"ops":[[1,0,1],[0,0,1],[1,0,1],[2,-1,-1],[1,0,1]]}
Output: [false,true,false]
Explanation: Query, union, rollback.

Constraints

• 1<=n<=10^5
• 1<=ops<=10^5

Asked by