$1$ All Links before Finds

Suppose that we use the disjoint$-$set union data structure for a sequence of $m$ Make$-$Set, Find$-$Set and Link operations, but we are told that all of the Link operations are performed before any FindSet operation. $($As usual, assume that there are $n$ Make$-$Set operations.$)$ Furthermore, suppose that we implement the data structure using both Union$-$by$-$Rank and Path Compression. Show that the total actual running time for all $m$ operations is $O(m).$

Note: Recall that the Link operation is given the two roots of the trees to be merged. Thus, you do not need to perform any Find$-$Set operations to execute a Link. $($This is just an exercise. It would be unclear how an application using this data structure would know which items are roots.$)$

Hint: Think about paying for the path compression during a Find$-$Set.

Note: There is no limit on the number of Find$-$Set operations. While we do know that $m$ is the total number of operations $($including Find$-$Sets$),$ you cannot assume a relationship between $m$ and the number of items $n.$ I.e$.,$ the number of Find$-$Set operations could greatly exceed the number of items $n.$

$2$ Offline Minimum

Do Problem $19-1$ in CLRS $($Problem $21-1$ in the third edition$),$ except in part a use the following sequence of operations:

$4,6,E,3,1,2,E,7,E,5,E,9,E,8,E,E$

Note: The premise of this problem is that you can turn the extract$-$min question around when the problem is offline. Instead of asking

Which item will this call to Extract$-$Min return?

you ask

Which Extract$-$Min call will return this item?

For example, if the item in question is $1($the smallest item$),$ then it will be returned by some call to Extract$-$Min $($unless $1$ is inserted after the last call to Extract$-$Min$).$ So$,$ the question is which call will return $1.$