import java.util.HashMap;

public class DisjointSet
{
  private HashMap<Integer, Integer> parent;
  private HashMap<Integer, Integer> rank;

  public DisjointSet()
  {
    this.parent = new HashMap<Integer, Integer>();
    this.rank = new HashMap<Integer, Integer>();
  } 

  public void newSet(int v)
  {
    parent.put(v, v);
    rank.put(v, 0);
  }

  public int find(int v)
  {
    int retval = 0;
    if(v == this.parent.get(v))
      retval =  v;
    else
    {
      parent.put(v, find(parent.get(v)));
    }
   return this.parent.get(v);
  }

  public void join(int v1, int v2)
  {
    int x = find(v1);
    int y = find(v2);
    if(x == y)
      return;
    if(this.rank.get(x) >  this.rank.get(y))
    {
      this.parent.put(y, x);
    }
    else if(this.rank.get(x) < this.rank.get(y))
    {
      this.parent.put(x ,y);
    }
    else //equal ranks
    {
      this.parent.put(x, y);
      int r = rank.get(v1);
      rank.put(y, rank.get(y) + 1);
    }
  }

  public static void main(String args[])
  {
    DisjointSet ds = new DisjointSet();
    for(int i = 0; i < 5; i++)
    {
      ds.newSet(i);
    }
    for(int i = 0; i < 5; i++)
      System.out.println(ds.find(i));
    ds.join(0, 1);
    ds.join(2, 3);
    System.out.println();
    for(int i = 0; i < 5; i++)
      System.out.println(ds.find(i));
    ds.join(0,3);
    ds.join(2,4);
    System.out.println();
    for(int i = 0; i < 5; i++)
      System.out.println(ds.find(i));
  }
}