Modify QuickUnionUF.java to include path compression, by adding a loop to find() that links every sie on the path from p to the root. Give a sequence of input pairs that causes this method to produce a path of length 4. Note: the amortized cost per operation for this algorithm is known to be logarithmic. Below is the QuickUnion.java code public class QuickUnionUF { private int[] parent; // parent[i] = parent of i private int count; // number of components /** * Initializes an empty union-find data structure with N isolated components 0 through N-1. * @throws java.lang.IllegalArgumentException if N < 0 * @param N the number of objects */ public QuickUnionUF(int N) { parent = new int[N]; count = N; for (int i = 0; i < N; i++) { parent[i] = i; } } /** * Returns the number of components. * @return the number of components (between 1 and N) */ public int count() { return count; } /** * Returns the component identifier for the component containing site p. * @param p the integer representing one site * @return the component identifier for the component containing site p * @throws java.lang.IndexOutOfBoundsException unless 0 <= p < N */ public int find(int p) { validate(p); while (p != parent[p]) p = parent[p]; return p; } // validate that p is a valid index private void validate(int p) { int N = parent.length; if (p < 0 || p >= N) { throw new IndexOutOfBoundsException("index " + p + " is not between 0 and " + N); } } /** * Are the two sites p and q in the same component? * @param p the integer representing one site * @param q the integer representing the other site * @return true if the sites p and q are in the same * component, and false otherwise * @throws java.lang.IndexOutOfBoundsException unless both 0 <= p < N and 0 <= q < N */ public boolean connected(int p, int q) { return find(p) == find(q); } /** * Merges the component containing sitep with the component * containing site q. * @param p the integer representing one site * @param q the integer representing the other site * @throws java.lang.IndexOutOfBoundsException unless both 0 <= p < N and 0 <= q < N */ public void union(int p, int q) { int rootP = find(p); int rootQ = find(q); if (rootP == rootQ) return; parent[rootP] = rootQ; count--; } /** * Reads in a sequence of pairs of integers (between 0 and N-1) from standard input, * where each integer represents some object; * if the objects are in different components, merge the two components * and print the pair to standard output. */ public static void main(String[] args) { int N = StdIn.readInt(); QuickUnionUF uf = new QuickUnionUF(N); while (!StdIn.isEmpty()) { int p = StdIn.readInt(); int q = StdIn.readInt(); if (uf.connected(p, q)) continue; uf.union(p, q); StdOut.println(p + " " + q); } StdOut.println(uf.count() + " components"); } }