import java.util.*;
import java.io.*;
public class QuickUnion {

	private int [] data;
	private int counts;
    // Initialize QuickUnion data structure with N nodes of the tree
	public QuickUnion (int N){
		counts =N;
        data= new int[N];
	for (int i=0; i<N; i++ )
		data[i]=i;
	}
    //chase the parent pointers until you reach to the root of the tree
    //is to be private not to be called to the client side
    private int root(int p){
        while(p!=data[p])p=data[p];

        return p;
    }
    // Connect the two pair to form one object
	public void union(int p,int q){
		// Get the coresponding root
		int i = root(p);
		int j = root(q);
		data[i]=j;
	}
	// Asks to find if two pair have the same root
	public boolean unionConnected(int p,int q){
		return root(p)==root(q);
	}
	
    // Counts the number of objects in the component
    public int count(){
    	return counts;
    }

    public static void main(String[] args)throws FileNotFoundException {
    	// Read data from the file one interger at a time
    	Scanner input = new Scanner(new File("tinyUF.txt"));
        
        // Now read the first interger from the file
        int N =input.nextInt();

        // create the UnionFind object
    	QuickUnion  qf = new QuickUnion (N);
    	// Read throught the whole file
    	while(input.hasNextInt()) {

    		// Read the first interger
    		int p = input.nextInt();
    		// Read the next interger
    		int q = input.nextInt();
    		if(!qf.unionConnected(p,q)){
    			qf.union(p,q);
    			System.out.println(p+" "+ q);
    		}

    	};
    }
	
}
@@ -97,24 +97,49 @@
 int counts;%0A
+    private int %5B%5D size;%0A
     // Initi
@@ -266,46 +266,241 @@
 N%5D;%0A
-%09for (int i=0; i%3CN; i++ )%0A%09%09data%5Bi%5D=i;
+        //to keep track of weighted list%0A        size = new int%5BN%5D;%0A%09for (int i=0; i%3CN; i++ )%0A%09%09data%5Bi%5D=i;%0A    for (int i=0;i%3CN ;i++ ) %7B%0A        // At first there is only one element in each index of an array%0A        size%5Bi%5D=1;%0A    %7D
 %0A%09%7D%0A
@@ -688,18 +688,132 @@
 %5Bp%5D)
-p=data%5Bp%5D;
+%7B%0A            %0A            //flaten the tree even futher%0A            data%5Bp%5D=data%5Bdata%5Bp%5D%5D;%0A            p=data%5Bp%5D;%0A        %7D
 %0A%0A  
@@ -987,20 +987,260 @@
 q);%0A
-%09%09data%5Bi%5D=j;
+        //if they have the same root return%0A        if(i==j)return;%0A        if(size%5Bi%5D %3C size%5Bj%5D)%7B%0A            data%5Bi%5D=j;%0A            size%5Bj%5D+=size%5Bj%5D;%0A        %7D else %7B%0A            data%5Bj%5D=i;%0A            size%5Bi%5D+=size%5Bj%5D;%0A        %7D%0A        counts--;%0A%09%09
 %0A%09%7D%0A

make the tree more flat