1. (20 pts = 5+5+5+5) This problem is related to disjoint set operations. Assume that we are using union by rank and find with path compression. Suppose that you are given a disjoint set structure described by the following array representation.

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
A	-3	1	1	3	1	5	5	7	-3	9	9	11	9	13	13	15

1. Suppose that you are starting with 16 disjoint sets obtained by

FOR i=1 to 16 DO make-set(i)

There are multiple sequences of find-set and union operations that will change these 16 disjoint sets to the one listed in the above. Find one such sequence, and list the last two union operations in your sequence.

2. Write the resulting array representation of the disjoint set structure after applying union(2, 10) to the given disjoint set structure.
3. Write the resulting array representation of the disjoint set structure after applying union(8, 14) to the given disjoint set structure (not the one after your operation).
4. Assume that you are dealing with n elements and m disjoint set operations including n make-set operations. Use asymptotic notation to denote the total time complexity of these m operations if union is by rank and find is with path compression.