class DisjointSetNode:
    def __init__(self, value):
        self.value = value
        self.parent = self
        self.rank = 0

# def make_set(x):
#     x.parent = x
#     x.rank = 0

def find_set(x):
    if x != x.parent:
        x.parent = find_set(x.parent)
    return x.parent

def union(x, y):
    link(find_set(x), find_set(y))

def link(x, y):
    if x.rank > y.rank:
        y.parent = x
    else:
        x.parent = y
        if x.rank == y.rank:
            y.rank = y.rank + 1

            
def main():
    x = "abcdef"
    y   = "ghij"

    set1 = make_tree(x)
    set2 = make_tree(y)

    test_union(set1)
    test_union(set2)

    print "List1"
    print_parent(set1)

    print "\nList2"
    print_parent(set2)

    union(set1[0], set2[0])
   
    print "\nUnion of two Sets"
    print_parent(set1)
    print_parent(set2)

def make_tree(values):
    result = []
    for v in values:
        result.append(DisjointSetNode(v))
    return result

def test_union(nodes):
    N = len(nodes)
    n = N / 2
    for i in xrange(n-1):
        union(nodes[i+1], nodes[i])
    for i in xrange(n, N-1):
        union(nodes[i], nodes[i+1])
    union(nodes[0], nodes[N-1])
    

def print_parent(nodes):
    for x in nodes:
        original_parent = x.parent.value
        set_parent = find_set(x)
        after_parent = x.parent.value
        print "Value:", x.value,
        print "  Original Parent:", original_parent,
        print "  Parent After Path Comparession:", after_parent
        
main()