#!/usr/bin/env python
#Author: Shriphani Palakodety
#Mail: spalakod@purdue.edu

valueNodeDict = {}

class Node():
	'''Represents a node in a tree'''
	def __init__(self, value, parent, rank):
		self.value = value
		self.parent = parent
		self.rank = rank
		valueNodeDict[value] = self

	def __str__(self):
		return str(value)

class Universe():
	'''The Universe where all sets sit'''
	def __init__(self):
		self.sets = [] #list of all root nodes
	
	def addSet(self, root):
		self.sets.append(root)
	
U = Universe()

def internalFindSet(x):
	'''Find The Root Of The Tree That Contains This Node. Uses path compression'''
	if x.parent is not x:
		x.parent = internalFindSet(x.parent)
	return x.parent

def MakeSet(x):
	'''Make a new node whose parent is itself'''
	a = Node(x, None, 0)
	a.parent = a
	U.addSet(a)

def FindSet(x):
	'''Returns the root of the tree which contains this value'''
	x_node = valueNodeDict[x]
	return internalFindSet(x_node)

def Union(x, y):
	'''Destructively Unite X and Y where x belongs to X and y to Y'''
	x_set = FindSet(x)
	y_set = FindSet(y)

	if x_set.rank > y_set.rank:
		y_set.parent = x_set
	else:
		x_set.parent = y_set
		if x_set.rank == y_set.rank:
			y_set.rank += 1