Write in java. Program a class called UnionFind for a union-find data structure that uses the smart union by size algorithm and path compression on find operations. Also, create a class called Graph for storing the edges of an undirected, weighted graph based on an adjacency list structure (see below). Your program will read from System.in and output to System.out UnionFind must implement the following methods:

Your program will read from System.in and output to System. out Union Find must implement the following methods Union Find (int n); creates a union find object for integers 0 union (int x, int y) if x and y are not already in the same set this call forms the union of the sets containing elements x and y using the union by size strategy. If x and y are elements of sets o the same s ize make the set containing x the dominant set int find (int y) returns the index of the root of the tree containing y Implements path compression on each call to find int numberofSets returns the number of disjoint sets remaining will either contain an "m'' command and nothing else, or w The input data begin with an "s" command followed by a series of other commands, one per line In the following descriptions of the commands n x and y are integers Create a UnionFind object for elements numbered from 0 to n-1 S n. and create an empty Graph object for n vertices all find on each of the two elements to see if they are already in the same set u x y If not, Call union(x,y) and print the index of the root then a space then the size of the resulting tree. Otherwise don't print anything Call find (x) and print the index of the root value f x Print a connectivity list as described below Create a Union Find class with elements 0,1 N*N-1 and a corresponding Graph object m N generate a grid graph as described below and print its edges The last command of a data file Boundary Conditions The last command in any input file is a line containing the character "e" followed by a newline character. There will never be more than one "m" command in a data file. The size of a Union Find data structure will not be more than 10,000 elements. No element index (x or y above) will ever occur in a data file that is outside 0 n-1]. The value of n will never be larger than 10,000. The value of N will never be larger than 100 The "c" command Output a connectivity list as follows (without the comments elements 0,2,3 are in the same set and 0 is the root 0 2 3 5 4 8 9 elements 5,4,8,9 are in the same set and 5 is the root element 7 is in a set on its own i.e. for each set, output its root value followed by a list of its other members in increasing order of integer value. The lines should be output in increasing order of the root value