Home

/* package codechef; // don't place package name! */

import java.util.; import java.lang.; import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */ class Codechef { static class DisjointSet { public Map<Long,Node> map =new HashMap<>();

class Node{
    long data;
    Node parent;
    int rank;
}
public void makeset (long data){
    Node node =new Node();
    node.data=data;
    node.parent= node;
    node.rank=1;
    map.put(data,node);
}
public boolean union (long data1,long data2){
    Node node1 = map.get(data1);
    Node node2 = map.get(data2);
    Node parent1 = findSet(node1);
    Node parent2 = findSet(node2);
    if(parent1.data == parent2.data)
    return false;

    if (parent1.rank >= parent2.rank){
        parent1.rank= parent1.rank+parent2.rank;
        parent2.parent=parent1;
    }
    else{
        parent2.rank=parent1.rank+parent2.rank;
        parent1.parent=parent2;
    }
    return true;
}

public long findSet(long data){
    return findSet(map.get(data)).data;
}
public Node findSet(Node node){
    Node parent = node.parent;
    if(parent == node)
    {
        return parent;
    }
    node.parent = findSet(node.parent);
    return node.parent;
}

/* public static void main(String args[]){ DisjointSet ds = new DisjointSet(); for(long i=1;i<8;++i) { ds.union(1, 2); ds.union(2, 3); ds.union(4, 5); ds.union(6, 7); ds.union(5, 6); ds.union(3, 7); } for(int i=1;i<8;++i) { System.out.println(ds.findSet(i)); } }*/ } public static void main (String[] args) throws java.lang.Exception { // your code goes here DisjointSet ds = new DisjointSet();

    for(long i=1;i<8;++i) {
       ds.makeset(i);
    }
        ds.union(1, 2);
        ds.union(2, 3);
        ds.union(4, 5);
        ds.union(6, 7);
        ds.union(5, 6);
        ds.union(3, 7);
        
        
    for(int i=1;i<8;++i)
    {
        System.out.println(ds.findSet(i)+"  "+(ds.map.get(ds.findSet(i))).rank );
    }
}

}