class TrieNode:
    def __init__(self):
        self.seen: dict[str, TrieNode] = {}
        self.word_end = False
    
    # Adds a node beneath the current node and returns it
    def add_node(self, character: str) -> Self:
        new_node = TrieNode()
        self.seen[character] = new_node
        return new_node
    
    # Returns a node if it exists beneath this node, otherwise None
    def get_node(self, character: str) -> Self | None:
        return self.seen.get(character)
        

class Trie:
    def __init__(self):
        self.nodes: dict[str, TrieNode] = {}
    
    def add_string(self, string: str):
        # Get the root node of this string
        c_1 = string[0]
        parent = self.nodes.get(string[0])
        
        # If it doesn't exist, create it
        if not parent:
            parent = TrieNode()
            self.nodes[c_1] = parent
            
        # Start at the parent, loop through the rest of the characters
        for i in range(1, len(string)):
            c_i = string[i]
            child_node = parent.get_node(c_i)
            
            # If a child node exists with this character, traverse to it
            if child_node:
                parent = child_node
            # Otherwise, we need to create it
            else:
                parent = parent.add_node(c_i)
        # Once we reach the end of the word, mark the final parent as the end of a word
        parent.word_end = True
                
    def search_string(self, string: str) -> bool:
        # Get the root node of this string
        root = self.nodes.get(string[0])
        
        # If there is no root node matching this string, return no match
        if not root:
            return False

        # If the string is only 1 character long or our root is a complete word
        if root.word_end or len(string) == 1:
            return True
        
        # Start at the root, loop through the rest of the characters
        parent = root
        for i in range(1, len(string)):
            # Get the next node in the tree
            parent = parent.get_node(string[i])
            
            # If there is no next node, then no prefix match exists
            if not parent:
                return False
                
            # If there is a next node and:
            #   1. If parent is a complete word, it is a prefix of our string
            #   3. If we have reached the end of our string, then it itself is a prefix of a seen word
            if parent.word_end or i == len(string) - 1:
                return True
            

def noPrefix(words):
    tree = Trie()
    for word in words:
        found = tree.search_string(word)
        if found:
            print("BAD SET")
            print(word)
            return
        else:
            tree.add_string(word)
    print("GOOD SET")