1. Given two arrays A and B with n elements each. e task is to make these two arrays identical, i.e., for each 1 i N, we want to make Ai = Bi . In a single operation, you can choose two integers x and y and replace all the occurrences of x in both the arrays with y. Notice that regardless of the number of occurrences replaced, it will still be counted as a single operation. Design an algorithm that outputs the minimum number of operation required. Analyze its time and space complexity

2. The least-common-ancestor (LCA) of two nodes u and v in a rooted tree T is the node w that is the ancestor of both u and v and also has the greatest depth in T. Consider the following code which assumes all nodes are colored white and that there is a collection of pairs of nodes P for which the LCAs are desired.

LCA(u)

Make-Set(u) ancestor[nd(u)] u for each child v of u in T LCA(v) union(nd(u),find (v)) ancestor[nd(u)] u color[u] = black for each node v st {u, v} is in P if color[v] = BLACK then output: LCA of u and v is ancestor[nd(v)]

Prove that this algorithm is correct and analyze its run-time assuming an ecient implementation of union-find