The dynamic-set operation UNION takes two disjoint sets \(S_1\) and \(S_2\) as input, and it returns a set \(S = S_1 \cup S_2\) consisting of all the elements of \(S_1\) and \(S_2\). The sets \(S_1\) and \(S_2\) are usually destroyed by the operation. Show how to support UNION in \(O(1)\) time using a suitable list data structure.

Suppose that both \(S_1\) and \(S_2\) are circular, doubly linked lists with sentinels. To perform a UNION operation on these two lists we do the following:

UNION-OPERATION-ON-CIRCULAR-DOUBLY-LINKED-LISTS-WITH-SENTINELS(x, y)

1 x.NIL.prev = y.tail

2 y.tail.next = x.NIL

3 x.tail.next = y.NIL.next

4 y.NIL.next.prev = x.tail

Calling this procedure on \(S_1\) and \(S_2\) effectively concatenates them together and removes the sentinel value from \(S_2\) so that there is only one sentinel value in the resulting doubly linked circular list.