class TreeNode:
    def __init__(self, nucloet, index):
        self.value = nucloet
        self.children = []
        self.index = index

    def addChild(self, childNode):
        self.children.append(childNode)

    def print(self, parentIndex):
        if self.value is not None:
            print(parentIndex, self.index, self.value)
        for child in self.children:
            child.print(self.index)


class Trie:
    def __init__(self):
        self.index = 1
        self.root = TreeNode(None,self.index)

    def addWord(self, word):
        current_node = self.root
        for value in word:
            found = False
            for child in current_node.children:
                if child.value== value:
                    current_node= child
                    found = True
                    break
            if not found:
                self.index +=1
                newNode = TreeNode(value, self.index)
                current_node.addChild(newNode)
                current_node = newNode

    def print(self):
        self.root.print(0)


def read() :
   dnas =[]
   f =open('rosalind_trie.txt')
   for line in f:
      line = line.replace('\n', '')
      dnas.append(line)
   return dnas
dnas = read()

trie = Trie()
for dna in dnas:
    trie.addWord(dna)

trie.print()