import time
import sys
f=open("in_sec21_8.txt","r")
items=f.readline().split(",")
w=open("out_r8_sec21_8.txt","w")
t0=time.clock()

class DisjointSets:
    def __init__(self):
        self.parent = {}
        self.rank = {}

    def make_set(self, x):
        self.parent[x] = x
        self.rank[x] = 0

    def find_set(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find_set(self.parent[x])
        return self.parent[x]

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

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

def test():
    dset = DisjointSets()
    w.write("Make sets")
    for x in items:
        dset.make_set(x)
    w.write("\n"+ "List parents"+"\n")
    for x in items:
        
        w.write (dset.find_set(x)+"\n")
    w.write("\n"+ "Union sets")
    for i in xrange(0,len(items),2):
        if i+1 < len(items):
            dset.union(items[i], items[i+1])
    w.write("\n"+ "List parents"+"\n")
    for x in items:
        w.write( dset.find_set(x)+"\n")

if __name__ == '__main__': test()

t1=time.clock()        
t2=t1-t0
w.write("Execution Time:-"+str(t2))
w.close()