Friendship Connectivity with Union-Find (+ fully dynamic follow-up)

There are n people labeled 0..n-1. You are given a sequence of operations to maintain friendships (undirected edges) and answer connectivity queries. Part 1 (main: additions only) Operations: add(a, b): add an undirected edge between a and b. query(a, b): return whether a and b are connected (in the same friend group). Design a data structure and process the operations, outputting an answer for each query. Part 2 (follow-up: breakups allowed) Add another operation: remove(a, b): delete the undirected edge between a and b. You still need to support query(a, b) connectivity queries. Discuss/design an approach for fully dynamic connectivity (both edge insertions and deletions). Constraints (typical) n and number of operations q up to 1e5. Example n=4 add(0,1), add(1,2), query(0,2) -> true remove(1,2), query(0,2) -> false Example Input n=4; ops=add 0 1; add 1 2; query 0 2; query 0 3 Output true false