import java.util.*;

class Node{
    int data;
    Node parent;
    int rank;
}

public class DisjointSet{
    private Map<Integer, Node> map;
    DisjointSet(){
        map = new HashMap<>();
    }

    public void makeSet(int data){
        Node node = new Node();
        node.data = data;
        node.parent = node;
        node.rank = 0;
        map.put(data, node);
    }

    private Node findSet(Node node){
        if(node.parent == node)
            return node;
        node.parent = findSet(node.parent);
        return node.parent;
    }

    public int findSet(int data){
        return findSet(map.get(data)).data;
    }

    public void union(int a, int b){
        Node node1 = map.get(a);
        Node node2 = map.get(b);
        Node representative1 = findSet(node1);
        Node representative2 = findSet(node2);
        if(representative1.data == representative2.data)
            return;
        if(representative1.rank >= representative2.rank){
            if(representative1.rank == representative2.rank)
                representative1.rank = representative2.rank + 1;
            representative2.parent = representative1;
        }
        else
            representative1.parent = representative2;
    }

    public static void main(String[] args){
        DisjointSet ds = new DisjointSet();
        for(int i=1; i<=7; 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<=7; i++)
            System.out.println(i +" -> " +ds.findSet(i));
    }
}