Modified Union Find Data Structure

The task is to make data structure with the following operations:

query: takes two arguments s and t and returns true if they are in the same set and false otherwise.

union: takes two arguments s and t and creates a union of the two sets that contain s and t such that if s is in S and t is in T it removes S and T and replaces it with the union of S and T.

move: takes two arguments s and t and takes s out of its current set and moves s and only s to the set containing t.

union and move don't do anything if s and t are in the same set.

My question is: how do you make an efficient version of this data structure that is < O(n²)?

• If everything but the last line is a third party task, please put in a block quote and tell who originated it and how you came to know it. Jun 7, 2021 at 20:09
• It's homework. I wouldn't know how
– user138448
Jun 7, 2021 at 20:32
• What's $n$? Is it the number of elements in your universe? Is the goal really that of implementing each operation in $o(n^2)$ time? Jun 9, 2021 at 10:13